Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25)

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