New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
share
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 coefficient in any constraint. Our main combinatorial result are improved support size bounds for ILPs. To improve granularity, we analyze for the largest 1-norm A_max of any column of the constraint matrix, instead of Δ. We show a support size upper bound of s≤ m·(log(3A_max)+√(log(A_max))), by deriving a new bound on the -1 branch of the Lambert 𝒲 function. Additionally, we provide a lower bound of mlog(A_max), proving our result asymptotically optimal. Furthermore, we give support bounds of the form s≤ 2m·log(1.46A_max). These improve upon the previously best constants by Aliev. et. al. (SIAM J. Optim., 2018), because all our upper bounds hold equally with A_max replaced by √(m)Δ. Using our combinatorial result, we obtain the fastest known approximation schemes (EPTAS) for the fundamental scheduling problem of makespan minimization of uniformly related machines (Q|| C_max).
READ FULL TEXT