Weighted online problems with advice

DOI10.1007/S00224-017-9806-5MaRDI QIDQ726104zbMATH OpenOpenAlexFDO

Authors Joan Boyar, Christian Kudahl, Jesper W. Mikkelsen, Lene M. Favrholdt

Publication date 3 August 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.05210

zbMATH Keywords

online algorithmsschedulingadvice complexityAOCweighted online problems

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Deterministic scheduling theory in operations research (90B35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: 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 maximum matching (giving better results than what follow from the general AOC results) and even non-AOC problems such as scheduling.

Recommendations

• Weighted Online Problems with Advice
• The advice complexity of a class of hard online problems
• Advice complexity for a class of online problems
• On the Advice Complexity of Online Problems
• Improved analysis of the online set cover problem with advice

Cites work

• Advice complexity for a class of online problems
• Advice complexity of the online induced subgraph problem
• Competitive paging with locality of reference
• Competitive snoopy caching
• LRU is better than FIFO
• Measuring the problem-relevant information in input
• On the Advice Complexity of Online Problems
• Online algorithms with advice for bin packing and scheduling problems
• Online bounded analysis
• Online computation with advice
• Randomization can be as helpful as a glimpse of the future in online computation
• The advice complexity of a class of hard online problems
• The string guessing problem as a method to prove lower bounds on the advice complexity

Cited in

(6)

• The advice complexity of a class of hard online problems
• Parallel solutions for ordinal scheduling with a small number of machines
• Weighted Online Problems with Advice
• Length-Weighted Disjoint Path Allocation
• Parallel solutions for preemptive makespan scheduling on two identical machines
• On the advice complexity of the online dominating set problem

This page was built for publication: Weighted online problems with advice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q726104)