Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
From MaRDI portal
Publication:3183480
DOI10.1007/978-3-642-03367-4_44zbMath1253.68357OpenAlexW2133668753MaRDI QIDQ3183480
Bruno Escoffier, Nicolas Bourgeois, Vangelis Th. Paschos
Publication date: 20 October 2009
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-03367-4_44
Related Items (7)
Moderately exponential approximation for makespan minimization on related machines ⋮ Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation ⋮ Capacitated domination faster than \(O(2^n)\) ⋮ Sparsification and subexponential approximation ⋮ Efficient algorithms for the \textsc{max~\(k\)-vertex cover problem} ⋮ Exact and approximate bandwidth ⋮ Approximation of min coloring by moderately exponential algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Vertex Cover: Further Observations and Further Improvements
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Proof verification and the hardness of approximation problems
- On Approximate Solutions for Combinatorial Optimization Problems
- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
- On Parameterized Approximability
- Parameterized Approximation Problems
- Set Partitioning via Inclusion-Exclusion
- Confronting hardness using a hybrid approach
- Vertex packings: Structural properties and algorithms
This page was built for publication: Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
