Inapproximability Results for Bounded Variants of Optimization Problems
- 1 January 2003
- book chapter
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 27-38
Abstract
No abstract availableKeywords
This publication has 10 references indexed in Scilit:
- Inapproximability Results for Bounded Variants of Optimization ProblemsLecture Notes in Computer Science, 2003
- On the Complexity of Approximating k-Dimensional MatchingLecture Notes in Computer Science, 2003
- Approximation Hardness of the Steiner Tree Problem on GraphsLecture Notes in Computer Science, 2002
- The importance of being biased2002
- Non-approximability results for optimization problems on bounded degree instances2001
- Some optimal inapproximability resultsJournal of the ACM, 2001
- On the approximability of the traveling salesman problem (extended abstract)2000
- Improved non-approximability results for minimum vertex cover with density constraintsTheoretical Computer Science, 1999
- Approximate graph coloring by semidefinite programmingJournal of the ACM, 1998
- On approximation properties of the Independent set problem for degree 3 graphs1995