Parameterized Resiliency Problems via Integer Linear Programming. / Crampton, Jason; Gutin, Gregory; Koutecky, Martin; Watrigant, Remi.

CIAC 2017, 10th International Conference on Algorithms and Complexity May 26, 2017 - May 28, 2017. Vol. 10236 Springer, 2017. p. 164-176 (Lecture Notes in Computer Science; Vol. 10236).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

E-pub ahead of print

Abstract

We introduce a framework in parameterized algorithms whose purpose is to solve resiliency versions of decision problems. In resiliency problems, 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 version of several concrete problems, and prove that they are FPT under natural parameterizations. Our first result, for a problem which is of interest in access control, subsumes several FPT results and solves an open question from Crampton et al. (AAIM 2016). The second concerns 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.

Gutin’s research was supported by Royal Society Wolfson Research Merit Award. Koutecký’s research was supported by projects 14-10003S of GA ČR and 338216 of GA UK.
Original languageEnglish
Title of host publicationCIAC 2017, 10th International Conference on Algorithms and Complexity May 26, 2017 - May 28, 2017
PublisherSpringer
Pages164-176
Number of pages13
Volume10236
ISBN (Electronic)978-3-319-57586-5
ISBN (Print)978-3-319-57585-8
DOIs
StateE-pub ahead of print - 14 Apr 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Cham
Volume10236
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 27517887