Advice complexity of priority algorithms
From MaRDI portal
Publication:5916086
DOI10.1007/978-3-030-04693-4_5zbMath1444.68298arXiv1806.06223OpenAlexW3022611370WikidataQ126802091 ScholiaQ126802091MaRDI QIDQ5916086
Joan. Boyar, Denis Pankratov, Allan Borodin, Kim S. Larsen
Publication date: 15 January 2019
Published in: Theory of Computing Systems, Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1806.06223
Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Online algorithms; streaming algorithms (68W27)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Online bin packing with advice
- Toward a model for backtracking and dynamic programming
- Greedy matching: guarantees and limitations
- Online algorithms with advice: the tape model
- The string guessing problem as a method to prove lower bounds on the advice complexity
- Models of greedy algorithms for graph problems
- Priority algorithms for graph optimization problems
- Bubblesearch: a simple heuristic for improving priority-based greedy algorithms
- On extensions of the deterministic online model for bipartite matching and max-sat
- (Incremental) priority algorithms
- Priority algorithms for makespan minimization in the subset model.
- The power of priority algorithms for facility location and set cover
- On the Advice Complexity of the k-Server Problem
- Bounds on Greedy Algorithms for MAX SAT
- Randomization Can Be as Helpful as a Glimpse of the Future in Online Computation
- The approximation of maximum subgraph problems
- Reducibility among Combinatorial Problems
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- The complexity of theorem-proving procedures
- Advice complexity of priority algorithms
This page was built for publication: Advice complexity of priority algorithms
