Parameterized resiliency problems via integer linear programming

DOI10.1007/978-3-319-57586-5_15zbMATH Open1486.68082DBLPconf/ciac/CramptonGKW17arXiv1605.08738OpenAlexW2962721539WikidataQ62044467 ScholiaQ62044467MaRDI QIDQ5283365FDOQ5283365

J. Crampton, Rémi Watrigant, Martin Koutecký, G. Gutin

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We introduce an extension of decision problems called resiliency 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 versions 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 version 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.

Full work available at URL: https://arxiv.org/abs/1605.08738

Recommendations

• Parameterized resiliency problems
• A multivariate approach for checking resiliency in access control
• The parameterized complexity and kernelization of resilience for database queries
• The complexity landscape of decompositional parameters for ILP
• Algorithms for stable and perturbation-resilient problems

Mathematics Subject Classification ID

Integer programming (90C10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Fundamentals of parameterized complexity
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• Parameterized Algorithms
• Parametric Integer Programming in Fixed Dimension
• An application of simultaneous diophantine approximation in combinatorial optimization
• Multivariate complexity analysis of Swap Bribery
• \(n\)-fold integer programming in cubic time
• Title not available (Why is that?)
• Bin packing with fixed number of bins revisited
• Polynomial kernels for weighted problems
• Elections with Few Candidates: Prices, Weights, and Covering Problems
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Integer plane multiflows with a mixed number of demands
• Scheduling and fixed-parameter tractability
• A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity
• A Multivariate Approach for Checking Resiliency in Access Control

Cited In (4)

• Parameterized resiliency problems
• Title not available (Why is that?)
• Integer programming in parameterized complexity: five miniatures
• Integer Programming in Parameterized Complexity: Three Miniatures.

This page was built for publication: Parameterized resiliency problems via integer linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283365)