Parameterized resiliency problems
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Parameterized resiliency problems
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA17-09142S" target="_blank" >GA17-09142S: Modern algorithms: New challenges of complex data sets</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2019
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
—
Volume of the periodical
2019
Issue of the periodical within the volume
795
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
14
Pages from-to
478-491
UT code for WoS article
000494887800037
EID of the result in the Scopus database
2-s2.0-85070724206