Options
New support size bounds for integer programming, applied to makespan minimization on uniformly related machines
Citation Link: https://doi.org/10.15480/882.8887
Publikationstyp
Conference Paper
Date Issued
2023
Sprache
English
Author(s)
Universität zu Kiel
Universität zu Kiel
First published in
Number in series
283
Article Number
13
Citation
International Symposium on Algorithms and Computation (ISAAC 2023) 283: 13
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing
ISBN
978-3-95977-289-1
Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows that any feasible integer linear program (ILP) has a solution with support size s ≤ 2m · log(4m∆), where m is the number of constraints, and ∆ is the largest absolute coefficient in any constraint.
Our main combinatorial result are improved support size bounds for ILPs. We show that any ILP has a solution with support size s ≤ m · (log(3A_{max}) + √(log(A_{max}))), where A_{max} := ∥A∥_1 denotes the 1-norm of the constraint matrix A. Furthermore, we show support bounds in the linearized form s ≤ 2m · log(1.46A_{max}). Our upper bounds also hold with A_{max} replaced by √m∆, which improves on the previously best constants in the linearized form. Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient.
We design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||Cmax). Our EPTAS yields a (1 + ε)-approximation for Q||Cmax on N jobs in time 2^O(1/ε log3(1/ε) log(log(1/ε))) + O(N), which improves over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020) with run time 2^O(1/ε log4(1/ε)) + N^O(1). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation which greatly benefits from the small support.
Our main combinatorial result are improved support size bounds for ILPs. We show that any ILP has a solution with support size s ≤ m · (log(3A_{max}) + √(log(A_{max}))), where A_{max} := ∥A∥_1 denotes the 1-norm of the constraint matrix A. Furthermore, we show support bounds in the linearized form s ≤ 2m · log(1.46A_{max}). Our upper bounds also hold with A_{max} replaced by √m∆, which improves on the previously best constants in the linearized form. Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient.
We design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||Cmax). Our EPTAS yields a (1 + ε)-approximation for Q||Cmax on N jobs in time 2^O(1/ε log3(1/ε) log(log(1/ε))) + O(N), which improves over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020) with run time 2^O(1/ε log4(1/ε)) + N^O(1). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation which greatly benefits from the small support.
Subjects
Integer programming
makespan minimization
scheduling algorithms
uniformly related machines
DDC Class
004: Computer Sciences
Publication version
publishedVersion
Loading...
Name
LIPIcs.ISAAC.2023.13.pdf
Type
Main Article
Size
901.88 KB
Format
Adobe PDF