• Home
• Conferences
• Current Member Societies
• EURO Working Groups
• Publications

EURO Bulletin Board - Webinars

[Scheduling seminar] Matthias Mnich (TU Hamburg) | May 29 | New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines

• https://schedulingseminar.com/

  Upcoming talks

  New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines 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(3∥A∥_1) + \sqrt{log(∥A∥_1)}), where ∥A∥_1 denotes the 1-norm of the constraint matrix A. Our upper bounds also hold with ∥A∥_1 replaced by \sqrt{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/ε log^3(1/ε) log(log(1/ε)))} + O(N), which improves exponentially over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation with small support size. [Presenter] Matthias Mnich (TU Hamburg) [Invited by] Dvir Shabtay (Ben Gurion Uni) UTC May 29, 13:00 Wed Prague May 29, 15:00 Wed New York May 29, 09:00 Wed Shanghai May 29, 21:00 Wed

  Machine Learning meets Selection Hyper-heuristics Abstract [Presenter] Ender Ozcan (Uni of Nottingham) [Invited by] Zdeněk Hanzálek (CTU in Prague) UTC Jun 12, 13:00 Wed Prague Jun 12, 15:00 Wed New York Jun 12, 09:00 Wed Shanghai Jun 12, 21:00 Wed

  Posted on 2024-04-05 by Sarah Fores