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.
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 language | English |
|---|---|
| Title of host publication | CIAC 2017, 10th International Conference on Algorithms and Complexity May 26, 2017 - May 28, 2017 |
| Publisher | Springer |
| Pages | 164-176 |
| Number of pages | 13 |
| Volume | 10236 |
| ISBN (Electronic) | 978-3-319-57586-5 |
| ISBN (Print) | 978-3-319-57585-8 |
| DOIs | |
| Publication status | E-pub ahead of print - 14 Apr 2017 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer, Cham |
| Volume | 10236 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |