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”

Integer programming in parameterized complexity: Five miniatures

Identifikátory výsledku

  • Kód výsledku v IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10453167" target="_blank" >RIV/00216208:11320/22:10453167 - isvavai.cz</a>

  • Nalezeny alternativní kódy

    RIV/00216208:11620/22:10453167 RIV/68407700:21240/22:00343692

  • Výsledek na webu

    <a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=T5-dd7eCd2" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=T5-dd7eCd2</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1016/j.disopt.2020.100596" target="_blank" >10.1016/j.disopt.2020.100596</a>

Alternativní jazyky

  • Jazyk výsledku

    angličtina

  • Název v původním jazyce

    Integer programming in parameterized complexity: Five miniatures

  • Popis výsledku v původním jazyce

    Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra&apos;s algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation. To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime f (k)poly(n). We focus on: Modeling: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used. Optimality program: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter; we show which algorithms and tricks are often useful for speed-ups. Minding the poly(n): reducing f (k) often has the unintended consequence of increasing poly(n); so we highlight the common trade-offs and show how to get the best of both worlds. Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for Capacitated Dominating Set, Sum Coloring, Max-q-Cut, and certain other coloring problems by modeling them as convex programs in fixed dimension, n-fold integer programs, bounded dual treewidth programs, indefinite quadratic programs in fixed dimension, parametric integer programs in fixed dimension, and 2-stage stochastic integer programs. (C) 2020 TheAuthor(s). Published by Elsevier B.V.

  • Název v anglickém jazyce

    Integer programming in parameterized complexity: Five miniatures

  • Popis výsledku anglicky

    Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra&apos;s algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation. To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime f (k)poly(n). We focus on: Modeling: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used. Optimality program: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter; we show which algorithms and tricks are often useful for speed-ups. Minding the poly(n): reducing f (k) often has the unintended consequence of increasing poly(n); so we highlight the common trade-offs and show how to get the best of both worlds. Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for Capacitated Dominating Set, Sum Coloring, Max-q-Cut, and certain other coloring problems by modeling them as convex programs in fixed dimension, n-fold integer programs, bounded dual treewidth programs, indefinite quadratic programs in fixed dimension, parametric integer programs in fixed dimension, and 2-stage stochastic integer programs. (C) 2020 TheAuthor(s). Published by Elsevier B.V.

Klasifikace

  • Druh

    J<sub>imp</sub> - Článek v periodiku v databázi Web of Science

  • 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

    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)

Ostatní

  • Rok uplatnění

    2022

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

    Discrete Optimization

  • ISSN

    1572-5286

  • e-ISSN

    1873-636X

  • Svazek periodika

    44

  • Číslo periodika v rámci svazku

    P1

  • Stát vydavatele periodika

    NL - Nizozemsko

  • Počet stran výsledku

    33

  • Strana od-do

    100596

  • Kód UT WoS článku

    000832713200004

  • EID výsledku v databázi Scopus

    2-s2.0-85088118525