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

DOI10.1016/J.TCS.2005.03.007MaRDI QIDQ557903zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Cristina Bazgan, Vangelis Th. Paschos, 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

CompletenessComplexityApproximation algorithmApproximation schemaCombinatorial optimizationReduction

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)

Recommendations

• Algorithms and Computation
• COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
• Completeness in approximation classes
• Mathematical Foundations of Computer Science 2003
• scientific article; zbMATH DE number 17535

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• Approximate solution of NP optimization problems
• Approximation algorithms for NP-complete problems on planar graphs
• Bridging gap between standard and differential polynomial approximation: The case of bin-packing
• COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
• Completeness in approximation classes
• Mathematical Foundations of Computer Science 2003
• On Syntactic versus Computational Views of Approximability
• On approximation scheme preserving reducibility and its applications
• On the Structure of Polynomial Time Reducibility
• Optimization, approximation, and complexity classes
• The Traveling Salesman Problem with Distances One and Two

Cited in

(21)

• Online admission control and embedding of service chains
• Approximation of min coloring by moderately exponential algorithms
• Efficient approximation of Min Set Cover by moderately exponential algorithms
• On fractional fragility rates of graph classes
• Mathematical Foundations of Computer Science 2003
• Dual parameterization and parameterized approximability of subset graph problems
• On complexity of the bilevel location and pricing problems
• On multi-path routing for reliable communications in failure interdependent complex networks
• Max-independent set and the quantum alternating operator ansatz
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• Polynomial approximation: a structural and operational study. (Abstract of thesis)
• 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
• COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
• Sublinear separators, fragility and subexponential expansion
• Algorithms and Computation
• Genetic local search and hardness of approximation for the server load balancing problem
• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
• How heavy independent sets help to find arborescences with many leaves in DAGs
• Completeness in approximation classes beyond APX
• Domination and convexity problems in the target set selection model

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

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