Advice complexity of adaptive priority algorithms

DOI10.1016/J.TCS.2023.114318arXiv1910.00868OpenAlexW2977477903MaRDI QIDQ6180750FDOQ6180750

Authors: Joan Boyar, Kim S. Larsen, Denis Pankratov 

Publication date: 2 January 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

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. We also 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.

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

zbMATH Keywords

online algorithmsexact algorithmsadvice complexitygreedy algorithmspriority algorithmsadaptive priority algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• A measure \& conquer approach for the analysis of exact algorithms
• Exact exponential algorithms.
• On the power of randomization in on-line algorithms
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Online graph exploration with advice
• Information complexity of online problems
• Title not available (Why is that?)
• Measuring the problem-relevant information in input
• Online computation with advice
• Tree exploration with advice
• Bounds for Certain Multiprocessing Anomalies
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Title not available (Why is that?)
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
• Online independent sets.
• Treasure hunt with advice
• On the advice complexity of online bipartite matching and online stable marriage
• Title not available (Why is that?)
• (Incremental) priority algorithms
• Priority algorithms for makespan minimization in the subset model.
• The power of priority algorithms for facility location and set cover
• Hard Knapsack Problems
• Toward a model for backtracking and dynamic programming
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• The string guessing problem as a method to prove lower bounds on the advice complexity
• Priority algorithms for graph optimization problems
• Bounds on greedy algorithms for MAX SAT
• Greedy matching: guarantees and limitations
• Models of greedy algorithms for graph problems
• Online algorithms with advice: the tape model
• Determining the Stability Number of a Graph
• Determining the Chromatic Number of a Graph
• Structural properties of greedoids
• Advice complexity of the online induced subgraph problem
• Title not available (Why is that?)
• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• Hierarchies for classes of priority algorithms for job scheduling
• Deterministic graph exploration with advice
• Bubblesearch: a simple heuristic for improving priority-based greedy algorithms
• Greedoids and Linear Objective Functions
• Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
• Advice complexity of maximum independent set in sparse and bipartite graphs
• Online Minimum Spanning Tree with Advice
• Advice complexity of priority algorithms

This page was built for publication: Advice complexity of adaptive priority algorithms

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