Advice complexity of adaptive priority algorithms
From MaRDI portal
Publication:6180750
DOI10.1016/j.tcs.2023.114318arXiv1910.00868OpenAlexW2977477903MaRDI QIDQ6180750
Joan. Boyar, Kim S. Larsen, Denis Pankratov
Publication date: 2 January 2024
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1910.00868
online algorithmsgreedy algorithmsexact algorithmsadvice complexitypriority algorithmsadaptive priority algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the advice complexity of online bipartite matching and online stable marriage
- Toward a model for backtracking and dynamic programming
- Greedy matching: guarantees and limitations
- Online algorithms with advice: the tape model
- Online computation with advice
- Structural properties of greedoids
- Exact exponential algorithms.
- The string guessing problem as a method to prove lower bounds on the advice complexity
- Hierarchies for classes of priority algorithms for job scheduling
- Models of greedy algorithms for graph problems
- Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
- Tree exploration with advice
- Priority algorithms for graph optimization problems
- Bubblesearch: a simple heuristic for improving priority-based greedy algorithms
- On the power of randomization in on-line algorithms
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- (Incremental) priority algorithms
- Priority algorithms for makespan minimization in the subset model.
- Online independent sets.
- The power of priority algorithms for facility location and set cover
- A sharp threshold in proof complexity yields lower bounds for satisfiability search
- Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
- Advice complexity of maximum independent set in sparse and bipartite graphs
- Online Graph Exploration with Advice
- Bounds on Greedy Algorithms for MAX SAT
- Greedoids and Linear Objective Functions
- A measure & conquer approach for the analysis of exact algorithms
- Treasure Hunt with Advice
- Information Complexity of Online Problems
- Hard Knapsack Problems
- Determining the Stability Number of a Graph
- Determining the Chromatic Number of a Graph
- Advice Complexity of the Online Induced Subgraph Problem
- Deterministic Graph Exploration with Advice
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- Measuring the problem-relevant information in input
- Bounds for Certain Multiprocessing Anomalies
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Online Minimum Spanning Tree with Advice
- Advice complexity of priority algorithms
This page was built for publication: Advice complexity of adaptive priority algorithms
