Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
DOI10.1016/J.TCS.2005.03.007zbMATH Open1068.68063DBLPjournals/tcs/BazganEP05OpenAlexW1978782513WikidataQ56335599 ScholiaQ56335599MaRDI QIDQ557903FDOQ557903
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
Recommendations
CompletenessComplexityApproximation algorithmApproximation schemaCombinatorial optimizationReduction
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- On the Structure of Polynomial Time Reducibility
- Approximation algorithms for NP-complete problems on planar graphs
- Title not available (Why is that?)
- The Traveling Salesman Problem with Distances One and Two
- Title not available (Why is that?)
- Bridging gap between standard and differential polynomial approximation: The case of bin-packing
- Approximate solution of NP optimization problems
- Completeness in approximation classes
- On Syntactic versus Computational Views of Approximability
- On approximation scheme preserving reducibility and its applications
- COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
- Mathematical Foundations of Computer Science 2003
Cited In (21)
- Approximation of min coloring by moderately exponential algorithms
- Efficient approximation of Min Set Cover by moderately exponential algorithms
- Mathematical Foundations of Computer Science 2003
- On fractional fragility rates of graph classes
- Dual parameterization and parameterized approximability of subset graph problems
- On complexity of the bilevel location and pricing problems
- Max-independent set and the quantum alternating operator ansatz
- On multi-path routing for reliable communications in failure interdependent complex networks
- 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
- COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
- A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
- Algorithms and Computation
- Sublinear separators, fragility and subexponential expansion
- 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
- Online admission control and embedding of service chains
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)
