On Some Tighter Inapproximability Results (Extended Abstract)
- 1 January 1999
- book chapter
- conference paper
- Published by Springer Science and Business Media LLC in Lecture Notes in Computer Science
- p. 200-209
- https://doi.org/10.1007/3-540-48523-6_17
Abstract
No abstract availableThis publication has 17 references indexed in Scilit:
- Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUTPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Approximation on the web: A compendium of NP optimization problemsLecture Notes in Computer Science, 1997
- Genome Rearrangements and Sorting by ReversalsSIAM Journal on Computing, 1996
- Fast sorting by reversalLecture Notes in Computer Science, 1996
- On the problem of sorting burnt pancakesDiscrete Applied Mathematics, 1995
- Derandomized graph productscomputational complexity, 1995
- Transforming cabbage into turnipPublished by Association for Computing Machinery (ACM) ,1995
- On approximation properties of the Independent set problem for degree 3 graphsLecture Notes in Computer Science, 1995
- On the complexity of approximating the independent set problemInformation and Computation, 1992
- Bounds for sorting by prefix reversalDiscrete Mathematics, 1979