Parameterized Resiliency Problems. / Crampton, Jason; Gutin, Gregory; Koutecky, Martin; Watrigant, Remi.

In: Theoretical Computer Science, 07.08.2019, p. 1-14.

Research output: Contribution to journalArticlepeer-review

E-pub ahead of print

Standard

Parameterized Resiliency Problems. / Crampton, Jason; Gutin, Gregory; Koutecky, Martin; Watrigant, Remi.

In: Theoretical Computer Science, 07.08.2019, p. 1-14.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Crampton, Jason ; Gutin, Gregory ; Koutecky, Martin ; Watrigant, Remi. / Parameterized Resiliency Problems. In: Theoretical Computer Science. 2019 ; pp. 1-14.

BibTeX

@article{f9d7004f5a0a411a8f0b737026f09986,
title = "Parameterized Resiliency Problems",
abstract = "We introduce an extension of decision problems called \textit{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 \textsc{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 {\sc 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 {\sc 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.",
author = "Jason Crampton and Gregory Gutin and Martin Koutecky and Remi Watrigant",
year = "2019",
month = aug,
day = "7",
doi = "10.1016/j.tcs.2019.08.002",
language = "English",
pages = "1--14",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Parameterized Resiliency Problems

AU - Crampton, Jason

AU - Gutin, Gregory

AU - Koutecky, Martin

AU - Watrigant, Remi

PY - 2019/8/7

Y1 - 2019/8/7

N2 - We introduce an extension of decision problems called \textit{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 \textsc{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 {\sc 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 {\sc 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.

AB - We introduce an extension of decision problems called \textit{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 \textsc{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 {\sc 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 {\sc 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.

U2 - 10.1016/j.tcs.2019.08.002

DO - 10.1016/j.tcs.2019.08.002

M3 - Article

SP - 1

EP - 14

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -