Parameterized resiliency problems

DOI10.1016/J.TCS.2019.08.002MaRDI QIDQ2330129zbMATH OpenOpenAlexFDO

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

Publication date 18 October 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.08.002

zbMATH Keywords

access controlclosest string problemcomputational biologydisjoint set coverfixed-parameter tractabilityparametric integer linear programmingresiliency problemssocial choice theory

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27) Integer programming (90C10) Sensitivity, stability, parametric optimization (90C31) Social choice (91B14)

Recommendations

• Parameterized resiliency problems via integer linear programming
• A multivariate approach for checking resiliency in access control
• The parameterized complexity and kernelization of resilience for database queries
• Algorithms for stable and perturbation-resilient problems
• Robust integer programming

Cites work

• \(n\)-fold integer programming in cubic time
• A multivariate approach for checking resiliency in access control
• A structural approach to kernels for ILPs: treewidth and total unimodularity
• An application of simultaneous diophantine approximation in combinatorial optimization
• Approximation Algorithms for the Graph Orientation Minimizing the Maximum Weighted Outdegree
• Bin packing with fixed number of bins revisited
• Complexity of short Presburger arithmetic
• Control and bribery in voting
• Decomposition of test sets in stochastic integer programming
• Elections with few candidates: prices, weights, and covering problems
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 4204116 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1305456 (Why is no real title available?)
• scientific article; zbMATH DE number 1557065 (Why is no real title available?)
• Integer plane multiflows with a mixed number of demands
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• Multivariate complexity analysis of Swap Bribery
• On covering problems of codes
• Parameterized algorithms
• Parameterized resiliency problems via integer linear programming
• Parametric integer programming in fixed dimension
• Scheduling
• Scheduling and fixed-parameter tractability
• Swap bribery
• Theory of computation.
• Voting and bribing in single-exponential time
• What's next? Future directions in parameterized complexity

Cited in

(6)

• The hardness of resilience for nested aggregation query
• On the complexity of resilience for aggregation queries
• A multivariate approach for checking resiliency in access control
• scientific article; zbMATH DE number 7564410 (Why is no real title available?)
• The extended BG-simulation and the characterization of t-resiliency
• Parameterized resiliency problems via integer linear programming

This page was built for publication: Parameterized resiliency problems

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