@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",
}