A survey on the structure of approximation classes
From MaRDI portal
Publication:458503
DOI10.1016/j.cosrev.2009.11.001zbMath1300.68031OpenAlexW2125294153MaRDI QIDQ458503
Vangelis Th. Paschos, Bruno Escoffier
Publication date: 7 October 2014
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://basepub.dauphine.fr/handle/123456789/3870
Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) 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 (3)
Priority-based bin packing with subset constraints ⋮ Approximating MAX SAT by moderately exponential and parameterized algorithms ⋮ Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Differential approximation of MIN SAT, MAX SAT and related problems
- The complexity of optimization problems
- Structure preserving reductions among convex optimization problems
- Non deterministic polynomial optimization problems and their approximations
- Bin packing can be solved within 1+epsilon in linear time
- On the complexity of approximating the independent set problem
- Optimization, approximation, and complexity classes
- Approximation algorithms for combinatorial problems
- A comparison of polynomial time reducibilities
- Differential approximation algorithms for some combinatorial optimization problems
- Zero knowledge and the chromatic number
- Logical definability of NP optimization problems
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- Polynomial approximation and graph-coloring
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Approximation algorithms for some vehicle routing problems
- On the differential approximation of MIN SET COVER
- The maximum saving partition problem
- Approximation algorithms for the traveling salesman problem
- Differential approximation results for the traveling salesman problem with distances 1 and 2
- Differential approximation for optimal satisfiability and related problems
- Approximation properties of NP minimization classes
- Max NP-completeness made easy
- Bridging gap between standard and differential polynomial approximation: The case of bin-packing
- On approximation scheme preserving reducibility and its applications
- Reductions, completeness and the hardness of approximability
- Improved low-degree testing and its applications
- Completeness in approximation classes beyond APX
- z-Approximations
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
- Handbook of Approximation Algorithms and Metaheuristics
- On Approximate Solutions for Combinatorial Optimization Problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- A Greedy Heuristic for the Set-Covering Problem
- On the Structure of Polynomial Time Reducibility
- P-Complete Approximation Problems
- On Syntactic versus Computational Views of Approximability
- Structure in Approximation Classes
- Approximation algorithms for NP-complete problems on planar graphs
- On the hardness of approximating minimization problems
- Interactive proofs and the hardness of approximating cliques
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
- The approximation of maximum subgraph problems
- Proving completeness by logic
- Some optimal inapproximability results
- The complexity of theorem-proving procedures
- COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
- The PCP theorem by gap amplification
This page was built for publication: A survey on the structure of approximation classes
