Inapproximability of Combinatorial Optimization Problems
Author:
- 13 February 2013
- book chapter
- Published by Wiley
- p. 381-434
Abstract
No abstract availableKeywords
All Related Versions
This publication has 157 references indexed in Scilit:
- Improved Low-Degree Testing and its ApplicationsCombinatorica, 2003
- Approximating CVP to Within Almost-Polynomial Factors is NP-HardCombinatorica, 2003
- Hardness of approximating the minimum distance of a linear codeIEEE Transactions on Information Theory, 2003
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- An algorithm for 3-colorable graphsInformation Processing Letters, 1997
- The geometry of graphs and some of its algorithmic applicationsCombinatorica, 1995
- Derandomized graph productscomputational complexity, 1995
- The complexity of the max word problem and the power of one-way interactive proof systemscomputational complexity, 1993
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975