Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness

DOI10.1016/j.tcs.2005.03.007zbMath1068.68063OpenAlexW1978782513WikidataQ56335599 ScholiaQ56335599MaRDI QIDQ557903

Vangelis Th. Paschos, Cristina Bazgan, Bruno Escoffier

Publication date: 30 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/3724

zbMATH Keywords

ComplexityCombinatorial optimizationApproximation algorithmCompletenessApproximation schemaReduction

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (18)

From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ Online Admission Control and Embedding of Service Chains ⋮ Polynomial approximation: a structural and operational study. (Abstract of thesis) ⋮ Genetic local search and hardness of approximation for the server load balancing problem ⋮ Sublinear separators, fragility and subexponential expansion ⋮ Domination and convexity problems in the target set selection model ⋮ Dual parameterization and parameterized approximability of subset graph problems ⋮ On fractional fragility rates of graph classes ⋮ PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs ⋮ How heavy independent sets help to find arborescences with many leaves in DAGs ⋮ Max-independent set and the quantum alternating operator ansatz ⋮ A survey on the structure of approximation classes ⋮ A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees ⋮ On multi-path routing for reliable communications in failure interdependent complex networks ⋮ Completeness in approximation classes beyond APX ⋮ Approximation of min coloring by moderately exponential algorithms ⋮ Efficient approximation of Min Set Cover by moderately exponential algorithms ⋮ On complexity of the bilevel location and pricing problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximate solution of NP optimization problems
• Completeness in approximation classes
• Optimization, approximation, and complexity classes
• Bridging gap between standard and differential polynomial approximation: The case of bin-packing
• On approximation scheme preserving reducibility and its applications
• On the Structure of Polynomial Time Reducibility
• On Syntactic versus Computational Views of Approximability
• Approximation algorithms for NP-complete problems on planar graphs
• The Traveling Salesman Problem with Distances One and Two
• Mathematical Foundations of Computer Science 2003
• COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES

This page was built for publication: Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness