The hardness of approximation: Gap location
- 1 June 1994
- journal article
- research article
- Published by Springer Nature in computational complexity
- Vol. 4 (2), 133-157
- https://doi.org/10.1007/bf01202286
Abstract
No abstract availableKeywords
This publication has 22 references indexed in Scilit:
- Linear approximation of shortest superstringsJournal of the ACM, 1994
- The hardness of approximation: Gap locationcomputational complexity, 1994
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- Maximum bounded 3-dimensional matching is MAX SNP-completeInformation Processing Letters, 1991
- The Steiner problem with edge lengths 1 and 2Information Processing Letters, 1989
- NP completeness of finding the chromatic index of regular graphsJournal of Algorithms, 1983
- P-Complete Approximation ProblemsJournal of the ACM, 1976
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976
- The Complexity of Near-Optimal Graph ColoringJournal of the ACM, 1976
- Planar 3-colorability is polynomial completeACM SIGACT News, 1973