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