Completeness in approximation classes beyond APX

DOI10.1016/j.tcs.2006.05.023zbMath1099.68135OpenAlexW2084935502MaRDI QIDQ2503307

Vangelis Th. Paschos, Bruno Escoffier

Publication date: 14 September 2006

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.05.023

zbMATH Keywords

complexitypolynomial approximationcompletenessreductionsNP-optimization problems

Mathematics Subject Classification ID

Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (7)

Algorithmic analysis of priority-based bin packing ⋮ Theoretical complexity of grid cover problems used in radar applications ⋮ And/or-convexity: a graph convexity based on processes and deadlock models ⋮ Genetic local search and hardness of approximation for the server load balancing problem ⋮ Priority-based bin packing with subset constraints ⋮ A survey on the structure of approximation classes ⋮ Parameterized approximation algorithms for some location problems in graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
• Completeness in approximation classes
• Optimization, approximation, and complexity classes
• Derandomized graph products
• On approximation scheme preserving reducibility and its applications
• Improved low-degree testing and its applications
• P-Complete Approximation Problems
• On Syntactic versus Computational Views of Approximability
• Structure in Approximation Classes

This page was built for publication: Completeness in approximation classes beyond APX