English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Mixed-integer linear programming (MILP) is at the core of many advancedalgorithms for solving fundamental problems in combinatorial optimization. Thecomplexity of solving MILPs directly correlates with their support size, whichis the minimum number of non-zero integer variables in an optimal solution. Ahallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows thatany feasible integer linear program (ILP) has a solution with support size$s\leq 2m\cdot\log(4m\Delta)$, where $m$ is the number of constraints, and$\Delta$ 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 anycolumn of the constraint matrix, instead of $\Delta$. We show a support sizeupper bound of $s\leq m\cdot(\log(3A_{\max})+\sqrt{\log(A_{\max})})$, byderiving a new bound on the -1 branch of the Lambert $\mathcal{W}$ function.Additionally, we provide a lower bound of $m\log(A_{\max})$, proving our resultasymptotically optimal. Furthermore, we give support bounds of the form $s\leq2m\cdot\log(1.46A_{\max})$. These improve upon the previously best constants byAliev. et. al. (SIAM J. Optim., 2018), because all our upper bounds holdequally with $A_{\max}$ replaced by $\sqrt{m}\Delta$.  Using our combinatorial result, we obtain the fastest known approximationschemes (EPTAS) for the fundamental scheduling problem of makespan minimizationof uniformly related machines ($Q\mid\mid C_{\max}$).

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