Parameterized resiliency problems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10403786" target="_blank" >RIV/00216208:11320/19:10403786 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Parameterized resiliency problems

Popis výsledku v původním jazyce

We introduce an extension of decision problems called resiliency problems. In a resiliency problem, the goal is to decide whether an instance remains positive after any (appropriately defined) perturbation has been applied to it. To tackle these kinds of problems, some of which might be of practical interest, we introduce a notion of resiliency for Integer Linear Programs (ILP) and show how to use a result of Eisenbrand and Shmonin (Math. Oper. Res., 2008) on Parametric Linear Programming to prove that ILP RESILIENCY is fixed-parameter tractable (FPT) under a certain parameterization. To demonstrate the utility of our result, we consider natural resiliency variants of several concrete problems, and prove that they are FPT under natural parameterizations. Our first results concern a four-variate problem which generalizes the DISJOINT SET COVER problem and which is of interest in access control. We obtain a complete parameterized complexity classification for every possible combination of the parameters. Then, we introduce and study a resiliency variant of the CLOSEST STRING problem, for which we extend an FPT result of Gramm et al. (Algorithmica, 2003). We also consider problems in the fields of scheduling and social choice. We believe that many other problems can be tackled by our framework. (C) 2019 Elsevier B.V. All rights reserved.

Název v anglickém jazyce

Parameterized resiliency problems

Popis výsledku anglicky

We introduce an extension of decision problems called resiliency problems. In a resiliency problem, the goal is to decide whether an instance remains positive after any (appropriately defined) perturbation has been applied to it. To tackle these kinds of problems, some of which might be of practical interest, we introduce a notion of resiliency for Integer Linear Programs (ILP) and show how to use a result of Eisenbrand and Shmonin (Math. Oper. Res., 2008) on Parametric Linear Programming to prove that ILP RESILIENCY is fixed-parameter tractable (FPT) under a certain parameterization. To demonstrate the utility of our result, we consider natural resiliency variants of several concrete problems, and prove that they are FPT under natural parameterizations. Our first results concern a four-variate problem which generalizes the DISJOINT SET COVER problem and which is of interest in access control. We obtain a complete parameterized complexity classification for every possible combination of the parameters. Then, we introduce and study a resiliency variant of the CLOSEST STRING problem, for which we extend an FPT result of Gramm et al. (Algorithmica, 2003). We also consider problems in the fields of scheduling and social choice. We believe that many other problems can be tackled by our framework. (C) 2019 Elsevier B.V. All rights reserved.

Druh

J_imp - Č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)

Projekt

<a href="/cs/project/GA17-09142S" target="_blank" >GA17-09142S: Moderní algoritmy: Nové výzvy komplexních dat</a><br>

Návaznosti

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

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ů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

2019

Číslo periodika v rámci svazku

795

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

14

Strana od-do

478-491

Kód UT WoS článku

000494887800037

EID výsledku v databázi Scopus

2-s2.0-85070724206