Tight Lower Bounds for Block-Structured Integer Programs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10493491" target="_blank" >RIV/00216208:11320/24:10493491 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/978-3-031-59835-7_17" target="_blank" >https://doi.org/10.1007/978-3-031-59835-7_17</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-59835-7_17" target="_blank" >10.1007/978-3-031-59835-7_17</a>
Alternative languages
Result language
angličtina
Original language name
Tight Lower Bounds for Block-Structured Integer Programs
Original language description
We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs admit a constraint matrix with independent blocks linked together by few constraints in a recursive pattern; and transposing their constraint matrix yields multi-stage IPs. The state-of-the-art algorithms to solve these IPs have an exponential gap in their running times, making it natural to ask whether this gap is inherent. We answer this question affirmative. Assuming the Exponential Time Hypothesis, we prove lower bounds showing that the exponential difference is necessary, and that the known algorithms are near optimal. Moreover, we prove unconditional lower bounds on the norms of the Graver basis, a fundamental building block of all known algorithms to solve these IPs. This shows that none of the current approaches can be improved beyond this bound.
Czech name
—
Czech description
—
Classification
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)
Result continuities
Project
<a href="/en/project/GA22-22997S" target="_blank" >GA22-22997S: Efficient and Realistic Models in Computational Social Choice</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2024
ISBN
978-3-031-59834-0
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
14
Pages from-to
224-237
Publisher name
SPRINGER INTERNATIONAL PUBLISHING AG
Place of publication
CHAM
Event location
Wroclaw
Event date
Jul 3, 2024
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001275732800017