Please use this identifier to cite or link to this item:
https://doi.org/10.15480/882.4606
Publisher DOI: | 10.1007/s10107-022-01882-9 | Title: | High multiplicity N-fold IP via configuration LP | Language: | English | Authors: | Knop, Dušan Koutecký, Martin Levin, Asaf Mnich, Matthias ![]() Onn, Shmuel |
Keywords: | Integer programming; Configuration IP; Fixed-parameter algorithms; Scheduling | Issue Date: | 21-Sep-2022 | Publisher: | Springer | Source: | Mathematical Programming (2022) | Abstract (english): | N-fold integer programs (IPs) form an important class of block-structured IPs for which increasingly fast algorithms have recently been developed and successfully applied. We study high-multiplicity N-fold IPs, which encode IPs succinctly by presenting a description of each block type and a vector of block multiplicities. Our goal is to design algorithms which solve N-fold IPs in time polynomial in the size of the succinct encoding, which may be significantly smaller than the size of the explicit (non-succinct) instance. We present the first fixed-parameter algorithm for high-multiplicity N-fold IPs, which even works for convex objectives. Our key contribution is a novel proximity theorem which relates fractional and integer optima of the Configuration LP, a fundamental notion by Gilmore and Gomory [Oper. Res., 1961] which we generalize. Our algorithm for N-fold IP is faster than previous algorithms whenever the number of blocks is much larger than the number of block types, such as in N-fold IP models for various scheduling problems. |
URI: | http://hdl.handle.net/11420/13427 | DOI: | 10.15480/882.4606 | ISSN: | 0025-5610 | Journal: | Mathematical programming | Institute: | Algorithmen und Komplexität E-11 | Document Type: | Article | Project: | Multivariate Algorithmen für Scheduling mit hoher Multiplizität Projekt DEAL |
Peer Reviewed: | Yes | License: | ![]() |
Appears in Collections: | Publications with fulltext |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
s10107-022-01882-9.pdf | Verlagsversion | 524,7 kB | Adobe PDF | View/Open![]() |
Page view(s)
119
checked on Jun 8, 2023
Download(s)
35
checked on Jun 8, 2023
Google ScholarTM
Check
Note about this record
Cite this record
Export
This item is licensed under a Creative Commons License