Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover

This work studies the inapproximability of two well-known scheduling problems: Concurrent Open Shop and the Assembly Line problem. For both these problems, Bansal and Khot [1] obtained tight (2 - ε)-factor inapproximability, assuming the Unique Games Conjecture (UGC). In this paper, we prove optimal (2 - ε)-factor NP-hardness of approximation for both these problems unconditionally, i.e., without assuming UGC. Our results for the scheduling problems follow from a structural hardness for Minimum Vertex Cover on hypergraphs - an unconditional but weaker analog of a similar result of Bansal and Khot [1] which, however, is based on UGC. Formally, we prove that for any ε > 0, and positive integers q, T > 1, the following is NP-hard: Given a qT-uniform hypergraph G(V, E), decide between the following cases, YES Case: There is a partition of V into V₁, ⋯, V_q, X with |V₁| = ⋯ = |V_q| ≥ (1 - ε/q) |V| such that the vertices of any hyperedge e can be partitioned into T blocks of q vertices each so that at least T - 1 of the blocks each contain at most one vertex from V_j, for any j ∈ [q]. Since T > 1, this implies that for any j ∈ [q], V_j ∪ X is a vertex cover of size at most (1/q + ε) |V|. NO Case: Every vertex cover in G has size at least (1 - ε)|V |. The above hardness result suffices to prove optimal inapproximability for the scheduling problems mentioned above, via black-box hardness reductions. Using this result, we also prove a super constant hardness factor for Two Stage Stochastic Vehicle Routing, for which a similar inapproximability was shown by Gørtz, Nagarajan, and Saket [2] assuming the UGC, and based on the result of [1].