On some tighter inapproximability results (extended abstract)

Piotr Berman, Marek Karpinski

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    173 Scopus citations


    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.

    Original languageEnglish (US)
    Title of host publicationAutomata, Languages and Programming - 26th International Colloquium, ICALP 1999, Proceedings
    PublisherSpringer Verlag
    Number of pages10
    ISBN (Print)3540662243, 9783540662242
    StatePublished - 1999
    Event26th International Colloquium on Automata, Languages and Programming, ICALP 1999 - Prague, Czech Republic
    Duration: Jul 11 1999Jul 15 1999

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume1644 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other26th International Colloquium on Automata, Languages and Programming, ICALP 1999
    Country/TerritoryCzech Republic

    All Science Journal Classification (ASJC) codes

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'On some tighter inapproximability results (extended abstract)'. Together they form a unique fingerprint.

    Cite this