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/ε
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.
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/
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
