(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F25%3A10511042" target="_blank" >RIV/00216208:11320/25:10511042 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1007/978-3-031-93112-3_22" target="_blank" >https://doi.org/10.1007/978-3-031-93112-3_22</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-031-93112-3_22" target="_blank" >10.1007/978-3-031-93112-3_22</a>
Alternative languages
Result language
angličtina
Original language name
(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
Original language description
We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: min{f(x) | Ax = b, l <= x <= u, x is an element of Z(n)}. The number of variables n is a variable part of the input, and we consider the regime where the constraint matrix A has small coefficients parallel to A parallel to(infinity) and small primal or dual treedepth tdP (A) or td(D)(A), respectively. Equivalently, we consider block-structured matrices, in particular n-fold, tree-fold, 2-stage and multi-stage matrices. We ask about the possibility of near-linear algorithms in the general case of (non-linear) separable convex functions. The techniques of previous works for the linear case are inherently limited to it; in fact, no strongly-polynomial algorithm may exist due to a simple unconditional information-theoretic lower bound of n log parallel to u - l parallel to(infinity), where l, u are the vectors of lower and upper bounds. Our first result is that with parameters td(P) (A) and parallel to A parallel to(infinity), this lower bound can be matched (up to dependency on the parameters). Second, with parameters td(D)(A) and parallel to A parallel to(infinity), the situation is more involved, and we design an algorithm with complexity g(td(D)(A), parallel to A parallel to(infinity))n log n log parallel to u - l parallel to(infinity) where g is some computable function. We conjecture that a stronger lower bound is possible in this regime, and our algorithm is in fact optimal. Our algorithms combine ideas from scaling, proximity, and sensitivity of integer programs, together with a new dynamic data structure allowing fast sparse updates.
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
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)
Others
Publication year
2025
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 2025
ISBN
978-3-031-93111-6
ISSN
0302-9743
e-ISSN
1611-3349
Number of pages
15
Pages from-to
297-311
Publisher name
SPRINGER INTERNATIONAL PUBLISHING AG
Place of publication
CHAM
Event location
Baltimore
Event date
Jun 11, 2025
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
001547306200022