Inapproximability of hypergraph vertex cover and applications to scheduling problems

N. Bansal, S. Khot

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    60 Citations (Scopus)

    Abstract

    Assuming the Unique Games Conjecture (UGC), we show optimal inapproximability results for two classic scheduling problems. We obtain a hardness of 2¿-¿e for the problem of minimizing the total weighted completion time in concurrent open shops. We also obtain a hardness of 2¿-¿e for minimizing the makespan in the assembly line problem. These results follow from a new inapproximability result for the Vertex Cover problem on k-uniform hypergraphs that is stronger and simpler than previous results. We show that assuming the UGC, for every k¿=¿2, the problem is inapproximable within k¿-¿e even when the hypergraph is almost k -partite.
    Original languageEnglish
    Title of host publicationAutomata, Languages and Programming (37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010. Proceedings, Part I)
    EditorsS. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, P.G. Spirakis
    Place of PublicationBerlin
    PublisherSpringer
    Pages250-261
    ISBN (Print)978-3-642-14164-5
    DOIs
    Publication statusPublished - 2010

    Publication series

    NameLecture Notes in Computer Science
    Volume6198
    ISSN (Print)0302-9743

    Fingerprint

    Dive into the research topics of 'Inapproximability of hypergraph vertex cover and applications to scheduling problems'. Together they form a unique fingerprint.

    Cite this