Toward a unified approach for the classification of NP-complete optimization problems

DOI10.1016/0304-3975(80)90006-7zbMath0442.68029OpenAlexW2053548601MaRDI QIDQ1143789

Marco Protasi, Alberto Marchetti-Spaccamela, Giorgio Ausiello

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90006-7

zbMATH Keywords

approximationNP-complete optimization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (17)

On different approximation criteria for subset product problems ⋮ New local search approximation techniques for maximum generalized satisfiability problems ⋮ An Improved Approximation Bound for Spanning Star Forest and Color Saving ⋮ Polynomial time approximation schemes and parameterized complexity ⋮ A better differential approximation ratio for symmetric TSP ⋮ On the complexity of approximating the independent set problem ⋮ Optimization, approximation, and complexity classes ⋮ Approximate solution of NP optimization problems ⋮ Local search, reducibility and approximability of NP-optimization problems ⋮ Improving known solutions is hard ⋮ Quantifiers and approximation ⋮ On the differential approximation of MIN SET COVER ⋮ On the complexity of approximating the independent set problem ⋮ Detection and localization of hidden radioactive sources with spatial statistical method ⋮ Parameterized computation and complexity: a new approach dealing with NP-hardness ⋮ Completeness in approximation classes ⋮ Differential approximation results for the traveling salesman problem with distances 1 and 2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Heuristic evaluation techniques for bin packing approximation algorithms
• Measuring the Quality of Approximate Solutions to Zero-One Programming Problems
• `` Strong NP-Completeness Results
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Limiting recursion

This page was built for publication: Toward a unified approach for the classification of NP-complete optimization problems