Optimal inapproximability for scheduling problems via structural hardness for hypergraph vertex cover

Abstract

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 [BK10] obtained tight (2-\eps)-factor inapproximability, assuming the Unique Games Conjecture (UGC). In this paper, we prove optimal (2-\eps)-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 hyper graphs - an unconditional but weaker analog of a similar result of Bansal and Khot [BK10] which, however, is based on UGC. Formally, we prove that for any \eps > 0, and positive integers q, T > 1, the following is NP-hard: Given a qT-uniform hyper graph G(V, E), decide between the following cases, Yes Case: There is a partition of V into V-1, V-q, X with |V-1|= =|V-q| >= (1-\eps)/q * |V| such that the vertices of any hyper edge 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\in [q]. Since T > 1, this implies that for any j \in [q], V-j \union X is a vertex cover of size at most (1/q +\eps) |V|. No Case: Every vertex cover in G has size at least (1-\eps)|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 [GNS12] assuming the UGC, and based on the result of [BK10]. © 2013 IEEE.