Toward a unified approach for the classification of NP-complete optimization problems
From MaRDI portal
Publication:1143789
DOI10.1016/0304-3975(80)90006-7zbMath0442.68029MaRDI QIDQ1143789
Alberto Marchetti-Spaccamela, Giorgio Ausiello, Marco Protasi
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
68Q25: Analysis of algorithms and problem complexity
Related Items
Approximate solution of NP optimization problems, Local search, reducibility and approximability of NP-optimization problems, Improving known solutions is hard, Completeness in approximation classes, Polynomial time approximation schemes and parameterized complexity, A better differential approximation ratio for symmetric TSP, On different approximation criteria for subset product problems, On the complexity of approximating the independent set problem, Optimization, approximation, and complexity classes, Quantifiers and approximation, New local search approximation techniques for maximum generalized satisfiability problems, On the differential approximation of MIN SET COVER, Differential approximation results for the traveling salesman problem with distances 1 and 2, Parameterized computation and complexity: a new approach dealing with NP-hardness, An Improved Approximation Bound for Spanning Star Forest and Color Saving
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
