Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F20%3A00342828" target="_blank" >RIV/68407700:21240/20:00342828 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1145/3397484" target="_blank" >https://doi.org/10.1145/3397484</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1145/3397484" target="_blank" >10.1145/3397484</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

Popis výsledku v původním jazyce

We consider the standard ILP Feasibility problem: given an integer linear program of the form {Ax = b, x >= 0}, where A is an integer matrix with k rows and ℓ columns, x is a vector of ℓ variables, and b is a vector of k integers, we ask whether there exists x element N ℓ that satisfies Ax = b. Each row of A specifies one linear constraint on x; our goal is to study the complexity of ILP Feasibility when both k, the number of constraints, and Ainfinity, the largest absolute value of an entry in A, are small. Papadimitriou was the first to give a fixed-parameter algorithm for ILP Feasibility under parameterization by the number of constraints that runs in time ((Ainfinity + binfinity) ⋅ k)O(k2). This was very recently improved by Eisenbrand and Weismantel, who used the Steinitz lemma to design an algorithm with running time (kAinfinity)O(k) ⋅ log binfinity, which was subsequently refined by Jansen and Rohwedder to O( kAinfinity)k ⋅ log ( Ainfinity + binfinity) ⋅ log Ainfinity. We prove that for {0, 1}-matrices A, the running time of the algorithm of Eisenbrand and Weismantel is probably optimal: an algorithm with running time 2o(k log k) ⋅ (ℓ + binfinity)o(k) would contradict the exponential time hypothesis. This improves previous non-tight lower bounds of Fomin et al. We then consider integer linear programs that may have many constraints, but they need to be structured in a "shallow" way. Precisely, we consider the parameter dual treedepth of the matrix A, denoted tdD(A), which is the treedepth of the graph over the rows of A, where two rows are adjacent if in some column they simultaneously contain a non-zero entry. It was recently shown by Koutecký et al. that ILP Feasibility can be solved in time Ainfinity2O(tdD(A)) ⋅ (k + ℓ + log binfinity)O(1). We present a streamlined proof of this fact and prove that, again, this running time is probably optimal: even assuming that all entries of A and b are in {-1, 0, 1}, the existence of an algorithm with running time 22o(tdD(A)) ⋅ (k + ℓ)O(1) would contradict the exponential time hypothesis.

Název v anglickém jazyce

Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

Popis výsledku anglicky

We consider the standard ILP Feasibility problem: given an integer linear program of the form {Ax = b, x >= 0}, where A is an integer matrix with k rows and ℓ columns, x is a vector of ℓ variables, and b is a vector of k integers, we ask whether there exists x element N ℓ that satisfies Ax = b. Each row of A specifies one linear constraint on x; our goal is to study the complexity of ILP Feasibility when both k, the number of constraints, and Ainfinity, the largest absolute value of an entry in A, are small. Papadimitriou was the first to give a fixed-parameter algorithm for ILP Feasibility under parameterization by the number of constraints that runs in time ((Ainfinity + binfinity) ⋅ k)O(k2). This was very recently improved by Eisenbrand and Weismantel, who used the Steinitz lemma to design an algorithm with running time (kAinfinity)O(k) ⋅ log binfinity, which was subsequently refined by Jansen and Rohwedder to O( kAinfinity)k ⋅ log ( Ainfinity + binfinity) ⋅ log Ainfinity. We prove that for {0, 1}-matrices A, the running time of the algorithm of Eisenbrand and Weismantel is probably optimal: an algorithm with running time 2o(k log k) ⋅ (ℓ + binfinity)o(k) would contradict the exponential time hypothesis. This improves previous non-tight lower bounds of Fomin et al. We then consider integer linear programs that may have many constraints, but they need to be structured in a "shallow" way. Precisely, we consider the parameter dual treedepth of the matrix A, denoted tdD(A), which is the treedepth of the graph over the rows of A, where two rows are adjacent if in some column they simultaneously contain a non-zero entry. It was recently shown by Koutecký et al. that ILP Feasibility can be solved in time Ainfinity2O(tdD(A)) ⋅ (k + ℓ + log binfinity)O(1). We present a streamlined proof of this fact and prove that, again, this running time is probably optimal: even assuming that all entries of A and b are in {-1, 0, 1}, the existence of an algorithm with running time 22o(tdD(A)) ⋅ (k + ℓ)O(1) would contradict the exponential time hypothesis.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/EF16_019%2F0000765" target="_blank" >EF16_019/0000765: Výzkumné centrum informatiky</a><br>

Návaznosti

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

Rok uplatnění

2020

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 periodika

ACM Transactions on Computation Theory

ISSN

1942-3454

e-ISSN

1942-3462

Svazek periodika

12

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

19

Strana od-do

"19:1"-"19:19"

Kód UT WoS článku

000583677700005

EID výsledku v databázi Scopus

2-s2.0-85088097305