Scheduling Kernels via Configuration LP

Result code in 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>

Alternative codes found

RIV/68407700:21240/22:00360610

Result on the web

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

Result language

angličtina

Original language name

Scheduling Kernels via Configuration LP

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

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

Publication year

2022

Confidentiality

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

Article name in the collection

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-247-1

ISSN

—

e-ISSN

—

Number of pages

15

Pages from-to

1-15

Publisher name

Schloss Dagstuhl

Place of publication

Dagstuhl

Event location

Berlin

Event date

Sep 5, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—