Vše

Co hledáte?

Vše
Projekty
Výsledky výzkumu
Subjekty

Rychlé hledání

  • Projekty podpořené TA ČR
  • Významné projekty
  • Projekty s nejvyšší státní podporou
  • Aktuálně běžící projekty

Chytré vyhledávání

  • Takto najdu konkrétní +slovo
  • Takto z výsledků -slovo zcela vynechám
  • “Takto můžu najít celou frázi”

Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F19%3A00334095" target="_blank" >RIV/68407700:21240/19:00334095 - isvavai.cz</a>

  • Výsledek na webu

    <a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2019.44" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.STACS.2019.44</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2019.44" target="_blank" >10.4230/LIPIcs.STACS.2019.44</a>

Alternativní jazyky

  • 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 Ji columns, x is a vector of Ji variables, and b is a vector of k integers, we ask whether there exists x E Ilk 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 MAILD.0, the largest absolute value of an entry in A, are small. Papadimitriou [29] was the first to give a fixed-parameter algorithm for ILP FEASIBILITY under parameterization by the number of constraints that runs in time ((MAIL, +1113110.0) " k) lk2). This was very recently improved by Eisenbrand and Weismantel [9], who used the Steinitz lemma to design an algorithm with running time (142410.) (k) "11b112, which was subsequently improved by Jansen and Rohwedder [17] to 0(14241o)k " log MbIfx,. 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 2 (k log k) " 14 0Y(k) would contradict the Exponential Time Hypothesis (ETH). This improves previous non-tight lower bounds of Fomin et al. [10]. 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 KouteckST 0 (td (A)) et al. [24] that ILP FEASIBILITY can be solved in time 112,1112 D (k loglIblfx,)(9(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 2' tdp (A)) " (k + f)(9(1) would contradict the ETH.

  • 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 Ji columns, x is a vector of Ji variables, and b is a vector of k integers, we ask whether there exists x E Ilk 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 MAILD.0, the largest absolute value of an entry in A, are small. Papadimitriou [29] was the first to give a fixed-parameter algorithm for ILP FEASIBILITY under parameterization by the number of constraints that runs in time ((MAIL, +1113110.0) " k) lk2). This was very recently improved by Eisenbrand and Weismantel [9], who used the Steinitz lemma to design an algorithm with running time (142410.) (k) "11b112, which was subsequently improved by Jansen and Rohwedder [17] to 0(14241o)k " log MbIfx,. 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 2 (k log k) " 14 0Y(k) would contradict the Exponential Time Hypothesis (ETH). This improves previous non-tight lower bounds of Fomin et al. [10]. 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 KouteckST 0 (td (A)) et al. [24] that ILP FEASIBILITY can be solved in time 112,1112 D (k loglIblfx,)(9(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 2' tdp (A)) " (k + f)(9(1) would contradict the ETH.

Klasifikace

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

Návaznosti výsledku

  • Projekt

  • Návaznosti

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Ostatní

  • Rok uplatnění

    2019

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

Údaje specifické pro druh výsledku

  • Název statě ve sborníku

    36th International Symposium on Theoretical Aspects of Computer Science, STACS 2019, March 13-16, 2019, Berlin, Germany

  • ISBN

    978-3-95977-100-9

  • ISSN

  • e-ISSN

    1868-8969

  • Počet stran výsledku

    15

  • Strana od-do

    "44:1"-"44:15"

  • Název nakladatele

    Schloss Dagstuhl - Leibniz Center for Informatics

  • Místo vydání

    Wadern

  • Místo konání akce

    Berlín

  • Datum konání akce

    13. 3. 2019

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

    WRD - Celosvětová akce

  • Kód UT WoS článku

    000472795800043