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

研究成果: Conference 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.

原文English
主出版物標題34th International Symposium on Algorithms and Computation, ISAAC 2023
編輯Satoru Iwata, Satoru Iwata, Naonori Kakimura
發行者Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN(電子)9783959772891
DOIs
出版狀態Published - 2023 12月
事件34th International Symposium on Algorithms and Computation, ISAAC 2023 - Kyoto, Japan
持續時間: 2023 12月 32023 12月 6

出版系列

名字Leibniz International Proceedings in Informatics, LIPIcs
283
ISSN(列印)1868-8969

Conference

Conference34th International Symposium on Algorithms and Computation, ISAAC 2023
國家/地區Japan
城市Kyoto
期間23-12-0323-12-06

All Science Journal Classification (ASJC) codes

  • 軟體

指紋

深入研究「On Min-Max Graph Balancing with Strict Negative Correlation Constraints」主題。共同形成了獨特的指紋。

引用此