Weighted Online Problems with Advice

Joan Boyar, Lene Monrad Favrholdt, Christian Kudahl, Jesper With Mikkelsen

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

Recently, the first online complexity class, AOC , was introduced. The class consists of many online problems where each request must be either accepted or rejected, and the aim is to either minimize or maximize the number of accepted requests, while maintaining a feasible solution. All AOC -complete problems (including Independent Set, Vertex Cover, Dominating Set, and Set Cover) have essentially the same advice complexity. In this paper, we study weighted versions of problems in AOC , i.e., each request comes with a weight and the aim is to either minimize or maximize the total weight of the accepted requests. In contrast to the unweighted versions, we show that there is a significant difference in the advice complexity of complete minimization and maximization problems. We also show that our algorithmic techniques for dealing with weighted requests can be extended to work for non-complete AOC problems such as Matching (giving better results than what follow from the general AOC results) and even non- AOC problems such as scheduling.
OriginalsprogEngelsk
TitelCombinatorial Algorithms : 27th International Workshop, IWOCA 2016
RedaktørerVeli Mäkinen, Simon J. Puglisi, Leena Salmela
ForlagSpringer
Publikationsdato2016
Sider179-190
ISBN (Trykt)978-3-319-44542-7
ISBN (Elektronisk)978-3-319-44543-4
DOI
StatusUdgivet - 2016
Begivenhed27th International Workshop on Combinatorial Algorithms - Helsinki, Finland
Varighed: 17. aug. 201619. aug. 2016

Konference

Konference27th International Workshop on Combinatorial Algorithms
LandFinland
ByHelsinki
Periode17/08/201619/08/2016
NavnLecture Notes in Computer Science
Vol/bind9843
ISSN0302-9743

Emneord

  • online algorithms
  • advice complexity
  • weighted problems
  • AOC

Citationsformater