Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation
From MaRDI portal
Publication:4596147
DOI10.1007/978-1-4614-5134-1_1zbMath1375.68070OpenAlexW94740613MaRDI QIDQ4596147
Publication date: 30 November 2017
Published in: Optimization Theory, Decision Making, and Operations Research Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-1-4614-5134-1_1
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms
- Exact exponential algorithms.
- Approximating the minimum maximal independence number
- Enumerating maximal independent sets with applications to graph colouring.
- Exact and approximate bandwidth
- Approximation of min coloring by moderately exponential algorithms
- Exponential-time approximation of weighted set cover
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Approximation algorithms for combinatorial problems
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Which problems have strongly exponential complexity?
- Fast algorithms for max independent set
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Combining Two Worlds: Parameterised Approximation for Vertex Cover
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- On Parameterized Approximability
- Parameterized Approximation Problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Fast Algorithms for min independent dominating set
- A Bottom-Up Method and Fast Algorithms for max independent set
- Capacitated Domination Faster Than O(2 n )
- Confronting hardness using a hybrid approach
- Exact Algorithms for Dominating Clique Problems
- An Exponential Time 2-Approximation Algorithm for Bandwidth
- Vertex packings: Structural properties and algorithms
- On approximation properties of the Independent set problem for degree 3 graphs
- Automata, Languages and Programming
