Completeness in approximation classes

DOI10.1016/0890-5401(91)90025-WzbMath0734.68039MaRDI QIDQ811119

Alessandro Panconesi, Pierluigi Crescenzi

Publication date: 1991

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

NP-complete problemspolynomial time approximation schemeapproximable problems within a constant

Mathematics Subject Classification ID

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

Related Items

A short note on the approximability of the maximum leaves spanning tree problem, Differential approximation results for the traveling salesman and related problems, The complexity and approximability of finding maximum feasible subsystems of linear relations, Approximation and online algorithms for multidimensional bin packing: a survey, The generalized definitions of the two-dimensional largest common substructure problems, On the approximability of some maximum spanning tree problems, On the approximability of some Maximum Spanning Tree Problems, Structure in approximation classes, Improved non-approximability results for vertex cover with density constraints, Local Monotonicity in Probabilistic Networks, Max NP-completeness made easy, Improved non-approximability results for minimum vertex cover with density constraints, A survey on the structure of approximation classes, On approximability of linear ordering and related NP-optimization problems on graphs., Polynomially bounded minimization problems which are hard to approximate, Reductions between scheduling problems with non-renewable resources and knapsack problems, Approximate solution of NP optimization problems, Local search, reducibility and approximability of NP-optimization problems, COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES, Structure of polynomial-time approximation, Quantifiers and approximation, Reductions, completeness and the hardness of approximability, Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s), Approximation of some NP-hard optimization problems by finite machines, in probability, Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness, Minimum monopoly in regular and tree graphs, Completeness in approximation classes beyond APX, Differential approximation of NP-hard problems with equal size feasible solutions, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, Some APX-completeness results for cubic graphs, Structural properties of bounded relations with an application to NP optimization problems, On the Hamming distance of constraint satisfaction problems., The maximum \(f\)-depth spanning tree problem, The complexity of theory revision

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On simple and creative sets in NP
• The complexity of optimization problems
• Structure preserving reductions among convex optimization problems
• Toward a unified approach for the classification of NP-complete optimization problems
• Non deterministic polynomial optimization problems and their approximations
• Approximation algorithms for combinatorial problems
• On the Structure of Polynomial Time Reducibility
• Algorithms for Scheduling Independent Tasks
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems