Please use this identifier to cite or link to this item:
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.
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: CC BY 4.0 (Attribution) CC BY 4.0 (Attribution)
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
s10107-022-01882-9.pdfVerlagsversion524,7 kBAdobe PDFView/Open
Show full item record

Page view(s)

checked on Jun 8, 2023


checked on Jun 8, 2023

Google ScholarTM


Note about this record

Cite this record


This item is licensed under a Creative Commons License Creative Commons