Completeness in approximation classes beyond APX

DOI10.1016/J.TCS.2006.05.023MaRDI QIDQ2503307zbMATH OpenOpenAlexFDO

Authors 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

completenesscomplexityNP-optimization problemspolynomial approximationreductions

Mathematics Subject Classification ID

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

Recommendations

• Completeness in approximation classes
• scientific article; zbMATH DE number 4030170
• COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
• Mathematical Foundations of Computer Science 2003
• Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
• Publication:3484351
• scientific article; zbMATH DE number 4029534
• Publication:4892553
• Complete sets and closeness to complexity classes

Cites work

• Completeness in approximation classes
• Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
• Derandomized graph products
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256762 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• Improved low-degree testing and its applications
• On approximation scheme preserving reducibility and its applications
• On Syntactic versus Computational Views of Approximability
• Optimization, approximation, and complexity classes
• P-Complete Approximation Problems
• Structure in Approximation Classes

Cited in

(8)

• 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
• scientific article; zbMATH DE number 17535 (Why is no real title available?)
• A survey on the structure of approximation classes
• Priority-based bin packing with subset constraints
• Proving the infeasibility of Horn formulas through read-once resolution
• Algorithmic analysis of priority-based bin packing

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2503307)