Toward a unified approach for the classification of NP-complete optimization problems
From MaRDI portal
Publication:1143789
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
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
