On Min-Max Graph Balancing with Strict Negative Correlation Constraints

Ting Yu Kuo, Yu Han Chen, Andrea Frosini, Sun Yuan Hsieh, Shi Chun Tsai, Mong Jen Kao

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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→ Z0 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.

Original languageEnglish
Title of host publication34th International Symposium on Algorithms and Computation, ISAAC 2023
EditorsSatoru Iwata, Satoru Iwata, Naonori Kakimura
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772891
Publication statusPublished - 2023 Dec
Event34th International Symposium on Algorithms and Computation, ISAAC 2023 - Kyoto, Japan
Duration: 2023 Dec 32023 Dec 6

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference34th International Symposium on Algorithms and Computation, ISAAC 2023

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'On Min-Max Graph Balancing with Strict Negative Correlation Constraints'. Together they form a unique fingerprint.

Cite this