Advice complexity of adaptive priority algorithms

Joan Boyar, Kim S. Larsen*, Denis Pankratov

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

15 Downloads (Pure)

Abstract

The priority model was introduced to capture “greedy-like” algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. As evidence that adding advice to adaptive priority algorithms extends both adaptive priority algorithms and online algorithms with advice, we present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7n/22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7n/22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way.

Original languageEnglish
Article number114318
JournalTheoretical Computer Science
Volume984
Number of pages31
ISSN0304-3975
DOIs
Publication statusPublished - 12. Feb 2024

Keywords

  • Adaptive priority algorithms
  • Advice complexity
  • Exact algorithms
  • Greedy algorithms
  • Online algorithms
  • Priority algorithms

Fingerprint

Dive into the research topics of 'Advice complexity of adaptive priority algorithms'. Together they form a unique fingerprint.

Cite this