2001 · 217 citations · 25 references
Natural SciencesComputer ScienceMathematicsCombinatoricsCombinatorial OptimizationComputational ComplexityOptimization TheoryInapproximability
par>We prove some non-approximability results for restrictions of basic combinatorial optimization problems to instances of bounded “degree&r dquo;or bounded “width.” Specifically:
25
Approximation Algorithms for NP-Hard Problems
Dorit S. Hochba · ACM SIGACT News · 1997 · 3.1K citations · Full text
A threshold of ln <i>n</i> for approximating set cover
Uriel Feige · Journal of the ACM · 1998 · 3.1K citations · Full text
A Greedy Heuristic for the Set-Covering Problem
Vašek Chvátal · Mathematics of Operations Research · 1979 · 2.6K citations