(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs

Kód výsledku v 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>

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs

Popis výsledku v původním jazyce

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 &lt;= x &lt;= 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.

Název v anglickém jazyce

(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs

Popis výsledku anglicky

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 &lt;= x &lt;= 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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2025

Kód důvěrnosti údajů

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

Název statě ve sborníku

INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2025

ISBN

978-3-031-93111-6

ISSN

0302-9743

e-ISSN

1611-3349

Počet stran výsledku

15

Strana od-do

297-311

Název nakladatele

SPRINGER INTERNATIONAL PUBLISHING AG

Místo vydání

CHAM

Místo konání akce

Baltimore

Datum konání akce

11. 6. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001547306200022