On Min-Max Graph Balancing with Strict Negative Correlation Constraints

We consider the min-max graph balancing problem with strict negative correlation (SNC) constraints. The graph balancing problem arises as an equivalent formulation of the classic unrelated machine scheduling problem, where we are given a hypergraph G = (V,E) with vertex-dependent edge weight function p: E × V 7→ Z≥0 that represents the processing time of the edges (jobs). The SNC constraints, which are given as edge subsets C1,C2, . . . ,Ck, require that the edges in the same subset cannot be assigned to the same vertex at the same time. Under these constraints, the goal is to compute an edge orientation (assignment) that minimizes the maximum workload of the vertices. In this paper, we conduct a general study on the approximability of this problem. First, we show that, in the presence of SNC constraints, the case with maxe∈E |e| = maxi |Ci| = 2 is the only case for which approximation solutions can be obtained. Further generalization on either direction, e.g., maxe∈E |e| or maxi |Ci|, will directly make computing a feasible solution an NP-complete problem to solve. Then, we present a 2-approximation algorithm for the case with maxe∈E |e| = maxi |Ci| = 2, based on a set of structural simplifications and a tailored assignment LP for this problem. We note that our approach is general and can be applied to similar settings, e.g., scheduling with SNC constraints to minimize the weighted completion time, to obtain similar approximation guarantees. Further cases are discussed to describe the landscape of the approximability of this prbolem. For the case with |V | ≤ 2, which is already known to be NP-hard, we present a fully-polynomial time approximation scheme (FPTAS). On the other hand, we show that the problem is at least as hard as vertex cover to approximate when |V | ≥ 3.