@inproceedings{15fd844b95234273beb0154cbbc3031f,

title = "Inapproximability of hypergraph vertex cover and applications to scheduling problems",

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.",

author = "N. Bansal and S. Khot",

year = "2010",

doi = "10.1007/978-3-642-14165-2_22",

language = "English",

isbn = "978-3-642-14164-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "250--261",

editor = "S. Abramsky and C. Gavoille and C. Kirchner and {Meyer auf der Heide}, F. and P.G. Spirakis",

booktitle = "Automata, Languages and Programming (37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010. Proceedings, Part I)",

address = "Germany",

}