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.
|Title of host publication||Automata, Languages and Programming (37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010. Proceedings, Part I)|
|Editors||S. Abramsky, C. Gavoille, C. Kirchner, F. Meyer auf der Heide, P.G. Spirakis|
|Place of Publication||Berlin|
|Publication status||Published - 2010|
|Name||Lecture Notes in Computer Science|