Scheduling Kernels via Configuration LP

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455462" target="_blank" >RIV/00216208:11320/22:10455462 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21240/22:00360610

Výsledek na webu

<a href="https://doi.org/10.4230/LIPIcs.ESA.2022.73" target="_blank" >https://doi.org/10.4230/LIPIcs.ESA.2022.73</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.ESA.2022.73" target="_blank" >10.4230/LIPIcs.ESA.2022.73</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Scheduling Kernels via Configuration LP

Popis výsledku v původním jazyce

Makespan minimization (on parallel identical or unrelated machines) is arguably the most natural and studied scheduling problem. A common approach in practical algorithm design is to reduce the size of a given instance by a fast preprocessing step while being able to recover key information even after this reduction. This notion is formally studied as kernelization (or simply, kernel) - a polynomial time procedure which yields an equivalent instance whose size is bounded in terms of some given parameter. It follows from known results that makespan minimization parameterized by the longest job processing time pmax has a kernelization yielding a reduced instance whose size is exponential in pmax. Can this be reduced to polynomial in pmax? We answer this affirmatively not only for makespan minimization, but also for the (more complicated) objective of minimizing the weighted sum of completion times, also in the setting of unrelated machines when the number of machine kinds is a parameter. Our algorithm first solves the Configuration LP and based on its solution constructs a solution of an intermediate problem, called huge N-fold integer programming. This solution is further reduced in size by a series 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 a polynomial reduction back to our scheduling problem, yielding a kernel. Our technique is highly novel in the context of kernelization, and our structural theorem about the Configuration LP is of independent interest. Moreover, we show a polynomial kernel for huge N-fold IP conditional on whether the so-called separation subproblem can be solved in polynomial time. Considering that integer programming does not admit polynomial kernels except for quite restricted cases, our &quot;conditional kernel&quot; provides new insight.

Název v anglickém jazyce

Scheduling Kernels via Configuration LP

Popis výsledku anglicky

Makespan minimization (on parallel identical or unrelated machines) is arguably the most natural and studied scheduling problem. A common approach in practical algorithm design is to reduce the size of a given instance by a fast preprocessing step while being able to recover key information even after this reduction. This notion is formally studied as kernelization (or simply, kernel) - a polynomial time procedure which yields an equivalent instance whose size is bounded in terms of some given parameter. It follows from known results that makespan minimization parameterized by the longest job processing time pmax has a kernelization yielding a reduced instance whose size is exponential in pmax. Can this be reduced to polynomial in pmax? We answer this affirmatively not only for makespan minimization, but also for the (more complicated) objective of minimizing the weighted sum of completion times, also in the setting of unrelated machines when the number of machine kinds is a parameter. Our algorithm first solves the Configuration LP and based on its solution constructs a solution of an intermediate problem, called huge N-fold integer programming. This solution is further reduced in size by a series 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 a polynomial reduction back to our scheduling problem, yielding a kernel. Our technique is highly novel in the context of kernelization, and our structural theorem about the Configuration LP is of independent interest. Moreover, we show a polynomial kernel for huge N-fold IP conditional on whether the so-called separation subproblem can be solved in polynomial time. Considering that integer programming does not admit polynomial kernels except for quite restricted cases, our &quot;conditional kernel&quot; provides new insight.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-247-1

ISSN

—

e-ISSN

—

Počet stran výsledku

15

Strana od-do

1-15

Název nakladatele

Schloss Dagstuhl

Místo vydání

Dagstuhl

Místo konání akce

Berlin

Datum konání akce

5. 9. 2022

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—