zbMATH — the first resource for mathematics

Inapproximability of hypergraph vertex cover and applications to scheduling problems. (English) Zbl 1287.90018
Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-14164-5/pbk). Lecture Notes in Computer Science 6198, 250-261 (2010).
Summary: Assuming the Unique Games Conjecture (UGC), we show optimal inapproximability results for two classic scheduling problems. We obtain a hardness of \(2 - \epsilon \) for the problem of minimizing the total weighted completion time in concurrent open shops. We also obtain a hardness of \(2 - \epsilon \) 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 \geq 2\), the problem is inapproximable within \(k - \epsilon \) even when the hypergraph is almost \(k \)-partite.
For the entire collection see [Zbl 1194.68005].

90B35 Deterministic scheduling theory in operations research
05C65 Hypergraphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX Cite
Full Text: DOI