Evader interdiction: algorithms, complexity and collateral damage

DOI10.1007/s10479-013-1372-xzbMath1303.90058arXiv1108.0894OpenAlexW1973266786WikidataQ34361359 ScholiaQ34361359MaRDI QIDQ490228

Kiyan Ahmadizadeh, Alexander Gutfraind, Matthew P. Johnson

Publication date: 22 January 2015

Published in: Annals of Operations Research (Search for Journal in Brave)

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

zbMATH Keywords

Markov chainnetwork interdictionfour color theorembridge policyminimal cutsubmodular set cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Discrete location and assignment (90B80)

Related Items (3)

Infrastructure security games ⋮ A decomposition approach for stochastic shortest-path network interdiction with goal threshold ⋮ Sequential Shortest Path Interdiction with Incomplete Information and Limited Feedback

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Primal-dual approximation algorithms for integral flow and multicut in trees
• The checkpoint problem
• Partial multicuts in trees
• On the positive-negative partial set cover problem
• Most vital links and nodes in weighted networks
• Some simplified NP-complete graph problems
• Maintenance of a piercing set for intervals with applications
• Fast stabbing of boxes in high dimensions
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Graph Algorithms
• Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
• A threshold of ln n for approximating set cover
• Polynomial flow-cut gaps and hardness of directed cut problems
• Improved approximation for directed cut problems
• Approximating the k-multicut problem
• Optimal Interdiction of Unreactive Markovian Evaders
• Greedy ${\ensuremath{\Delta}}$ -Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost
• The Maximum Coverage Location Problem
• Finding the n Most Vital Links in Flow Networks
• Finding the n Most Vital Nodes in a Flow Network
• Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs
• Submodular Function Minimization under Covering Constraints
• Finding All the Elementary Circuits of a Directed Graph
• Optimal interdiction of a supply network
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: Evader interdiction: algorithms, complexity and collateral damage