Polynomially bounded minimization problems which are hard to approximate
- 1 January 1993
- book chapter
- Published by Springer Nature
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- On the approximability of the maximum common subgraph problemPublished by Springer Nature ,1992
- On the complexity of approximating the independent set problemInformation and Computation, 1992
- Proof verification and hardness of approximation problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Completeness in approximation classesInformation and Computation, 1991
- On approximating the minimum independent dominating setInformation Processing Letters, 1991
- Quantifiers and approximationPublished by Association for Computing Machinery (ACM) ,1990
- The complexity of optimization problemsJournal of Computer and System Sciences, 1988
- Relations Among Complexity MeasuresJournal of the ACM, 1979
- Fast Approximation Algorithms for the Knapsack and Sum of Subset ProblemsJournal of the ACM, 1975