COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES

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)

zbMATH Keywords

complexitypolynomial approximationapproximation algorithmcompletenessapproximation class

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

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