Inapproximability of hypergraph vertex cover and applications to scheduling problems

N. Bansal, S. Khot

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    66 Citaten (Scopus)


    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.
    Originele taal-2Engels
    TitelAutomata, Languages and Programming (37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010. Proceedings, Part I)
    RedacteurenS. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, P.G. Spirakis
    Plaats van productieBerlin
    ISBN van geprinte versie978-3-642-14164-5
    StatusGepubliceerd - 2010

    Publicatie series

    NaamLecture Notes in Computer Science
    ISSN van geprinte versie0302-9743


    Duik in de onderzoeksthema's van 'Inapproximability of hypergraph vertex cover and applications to scheduling problems'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit