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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Makespan minimization (on parallel identical or unrelated machines) isarguably the most natural and studied scheduling problem. A common approach inpractical algorithm design is to reduce the size of a given instance by a fastpreprocessing step while being able to recover key information even after thisreduction. This notion is formally studied as kernelization (or simply, kernel)-- a polynomial time procedure which yields an equivalent instance whose sizeis bounded in terms of some given parameter. It follows from known results thatmakespan minimization parameterized by the longest job processing time$p_{\max}$ has a kernelization yielding a reduced instance whose size isexponential in $p_{\max}$. Can this be reduced to polynomial in $p_{\max}$?  We answer this affirmatively not only for makespan minimization, but also forthe (more complicated) objective of minimizing the weighted sum of completiontimes, also in the setting of unrelated machines when the number of machinekinds is a parameter. Our algorithm first solves the Configuration LP and basedon its solution constructs a solution of an intermediate problem, called huge$N$-fold integer programming. This solution is further reduced in size by aseries of steps, until its encoding length is polynomial in the parameters.Then, we show that huge $N$-fold IP is in NP, which implies that there is apolynomial reduction back to our scheduling problem, yielding a kernel.  Our technique is highly novel in the context of kernelization, and ourstructural theorem about the Configuration LP is of independent interest.Moreover, we show a polynomial kernel for huge $N$-fold IP conditional onwhether the so-called separation subproblem can be solved in polynomial time.Considering that integer programming does not admit polynomial kernels exceptfor quite restricted cases, our "conditional kernel" provides new insight.

Scheduling Kernels via Configuration LP