A survey on the structure of approximation classes
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)
Recommendations
Cites work
- z-approximations
- A comparison of polynomial time reducibilities
- A Greedy Heuristic for the Set-Covering Problem
- A threshold of ln n for approximating set cover
- Approximation algorithms for combinatorial problems
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- Approximation algorithms for NP-complete problems on planar graphs
- Approximation algorithms for some vehicle routing problems
- Approximation algorithms for the traveling salesman problem
- Approximation properties of NP minimization classes
- Asymptotic differential approximation ratio: Definitions, motivations and application to some combinatorial problems
- Bin packing can be solved within 1+epsilon in linear time
- Bridging gap between standard and differential polynomial approximation: The case of bin-packing
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Completeness in approximation classes
- Completeness in approximation classes beyond APX
- COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
- Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness
- Differential approximation algorithms for some combinatorial optimization problems
- Differential approximation for optimal satisfiability and related problems
- Differential approximation of MIN SAT, MAX SAT and related problems
- Differential approximation results for the traveling salesman problem with distances 1 and 2
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Handbook of Approximation Algorithms and Metaheuristics
- scientific article; zbMATH DE number 447044 (Why is no real title available?)
- scientific article; zbMATH DE number 3727583 (Why is no real title available?)
- scientific article; zbMATH DE number 3733262 (Why is no real title available?)
- scientific article; zbMATH DE number 3758364 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- 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 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1559563 (Why is no real title available?)
- scientific article; zbMATH DE number 3999286 (Why is no real title available?)
- scientific article; zbMATH DE number 751135 (Why is no real title available?)
- scientific article; zbMATH DE number 861333 (Why is no real title available?)
- scientific article; zbMATH DE number 2221549 (Why is no real title available?)
- Improved low-degree testing and its applications
- Interactive proofs and the hardness of approximating cliques
- Logical definability of NP optimization problems
- Max NP-completeness made easy
- Maximizing the number of unused bins
- Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
- Non deterministic polynomial optimization problems and their approximations
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- On Approximate Solutions for Combinatorial Optimization Problems
- On approximation scheme preserving reducibility and its applications
- On Syntactic versus Computational Views of Approximability
- On the complexity of approximating the independent set problem
- On the differential approximation of MIN SET COVER
- On the hardness of approximating minimization problems
- On the Structure of Polynomial Time Reducibility
- Optimization, approximation, and complexity classes
- P-Complete Approximation Problems
- Polynomial approximation and graph-coloring
- Proof verification and the hardness of approximation problems
- Proving completeness by logic
- Reductions, completeness and the hardness of approximability
- Some optimal inapproximability results
- Structure in Approximation Classes
- Structure preserving reductions among convex optimization problems
- The approximation of maximum subgraph problems
- The complexity of optimization problems
- The complexity of theorem-proving procedures
- The maximum saving partition problem
- The PCP theorem by gap amplification
- Zero knowledge and the chromatic number
Cited in
(5)- Approximation algorithms for minimizing the maximum lateness and makespan on parallel machines
- Structure in Approximation Classes
- Approximating MAX SAT by moderately exponential and parameterized algorithms
- scientific article; zbMATH DE number 5263318 (Why is no real title available?)
- Priority-based bin packing with subset constraints
This page was built for publication: A survey on the structure of approximation classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458503)
