New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines

Sebastian Berndt, Hauke Brinkop, Klaus Jansen +2

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 d…