Reductions, completeness and the hardness of approximability
From MaRDI portal
Publication:2488898
DOI10.1016/j.ejor.2005.06.006zbMath1111.90092OpenAlexW2011285766MaRDI QIDQ2488898
Vangelis Th. Paschos, Giorgio Ausiello
Publication date: 16 May 2006
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejor.2005.06.006
Combinatorial optimizationPolynomial approximationComplexity theoryComputing science\(\mathbf {NP}\)-hard optimization problemsApproximation preserving reductionCompleteness in approximation classes
Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)
Related Items
Hardness results for homology localization ⋮ A survey on the structure of approximation classes ⋮ The complexity of dissociation set problems in graphs ⋮ Approximation algorithms for the transportation problem with market choice and related models ⋮ Approximability and Exact Resolution of the Multidimensional Binary Vector Assignment Problem
Cites Work
- Approximate solution of NP optimization problems
- Completeness in approximation classes
- Structure preserving reductions among convex optimization problems
- Non deterministic polynomial optimization problems and their approximations
- Optimization, approximation, and complexity classes
- Approximation algorithms for combinatorial problems
- Differential approximation algorithms for some combinatorial optimization problems
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- Polynomial approximation algorithms with performance guarantees: an introduction-by-example
- On Approximate Solutions for Combinatorial Optimization Problems
- On Syntactic versus Computational Views of Approximability
- Structure in Approximation Classes
- Gadgets, Approximation, and Linear Programming
- Mathematical Foundations of Computer Science 2003
- Bounds on Multiprocessing Timing Anomalies
- The complexity of theorem-proving procedures
- Algorithms and Computation
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
