TY - GEN
T1 - On some tighter inapproximability results (extended abstract)
AU - Berman, Piotr
AU - Karpinski, Marek
PY - 1999
Y1 - 1999
N2 - We give a number of improved inapproximability results, including the best up to date explicit approximation thresholds for bo- unded occurence satisfiability problems like MAX-2SAT and E2-LIN-2, and the bounded degree graph problems, like MIS, Node Cover, and MAX CUT. We prove also for the first time inapproximability of the problem of Sorting by Reversals and display an explicit approximation threshold.
AB - We give a number of improved inapproximability results, including the best up to date explicit approximation thresholds for bo- unded occurence satisfiability problems like MAX-2SAT and E2-LIN-2, and the bounded degree graph problems, like MIS, Node Cover, and MAX CUT. We prove also for the first time inapproximability of the problem of Sorting by Reversals and display an explicit approximation threshold.
UR - http://www.scopus.com/inward/record.url?scp=84887471044&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84887471044&partnerID=8YFLogxK
U2 - 10.1007/3-540-48523-6_17
DO - 10.1007/3-540-48523-6_17
M3 - Conference contribution
AN - SCOPUS:84887471044
SN - 3540662243
SN - 9783540662242
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 200
EP - 209
BT - Automata, Languages and Programming - 26th International Colloquium, ICALP 1999, Proceedings
PB - Springer Verlag
T2 - 26th International Colloquium on Automata, Languages and Programming, ICALP 1999
Y2 - 11 July 1999 through 15 July 1999
ER -