Dear scheduling researcher,
We are delighted to announce the talk given by Matthias Mnich (TU
Hamburg).
The title is " New Support Size Bounds for Integer Programming,
Applied to Makespan Minimization on Uniformly Related Machines ".
The seminar will take place on Zoom on Wednesday, May 29 at 13:00
UTC.
Please be aware of summertime.
Join Zoom Meeting
https://cesnet.zoom.us/j/93008634528?pwd=b0JuTWdLaVpINFM3VGZPVFUydzIydz09
Meeting ID: 930 0863 4528
Passcode: 089440
You can follow the seminar online or offline on our Youtube
channel as well:
https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A
The abstract follows.
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/ε log3(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.
The next talk in our series will be:
Ender Ozcan (Uni of Nottingham) | Jun 12 | Machine Learning meets
Selection Hyper-heuristics
For more details, please visit https://schedulingseminar.com/
With kind regards
Zdenek, Mike and Guohua
-- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/