TY - GEN
T1 - On Min-Max Graph Balancing with Strict Negative Correlation Constraints
AU - Kuo, Ting Yu
AU - Chen, Yu Han
AU - Frosini, Andrea
AU - Hsieh, Sun Yuan
AU - Tsai, Shi Chun
AU - Kao, Mong Jen
N1 - Publisher Copyright:
© Ting-Yu Kuo, Yu-Han Chen, Andrea Frosini, Sun-Yuan Hsieh, Shi-Chun Tsai, and Mong-Jen Kao; licensed under Creative Commons License CC-BY 4.0.
PY - 2023/12
Y1 - 2023/12
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85179130358&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85179130358&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2023.50
DO - 10.4230/LIPIcs.ISAAC.2023.50
M3 - Conference contribution
AN - SCOPUS:85179130358
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 34th International Symposium on Algorithms and Computation, ISAAC 2023
A2 - Iwata, Satoru
A2 - Iwata, Satoru
A2 - Kakimura, Naonori
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 34th International Symposium on Algorithms and Computation, ISAAC 2023
Y2 - 3 December 2023 through 6 December 2023
ER -