COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
From MaRDI portal
Publication:5714673
DOI10.1142/S0129054105003807zbMath1081.68121MaRDI QIDQ5714673
Marc Demange, Vangelis Th. Paschos, Giorgio Ausiello, Cristina Bazgan
Publication date: 15 December 2005
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Related Items (4)
A 3/4 differential approximation algorithm for traveling salesman problem ⋮ Data reductions and combinatorial bounds for improved approximation algorithms ⋮ A survey on the structure of approximation classes ⋮ Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Differential approximation results for the traveling salesman and related problems
- Approximate solution of NP optimization problems
- Local search, reducibility and approximability of NP-optimization problems
- Completeness in approximation classes
- Structure preserving reductions among convex optimization problems
- Optimization, approximation, and complexity classes
- Differential approximation algorithms for some combinatorial optimization problems
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- Differential approximation for optimal satisfiability and related problems
- On approximation scheme preserving reducibility and its applications
- z-Approximations
- Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
- On Syntactic versus Computational Views of Approximability
- Structure in Approximation Classes
This page was built for publication: COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES