DOE OSTI · 985896
Matrix interdiction problem
Abstract
In the matrix interdiction problem, a real-valued matrix and an integer k is given. The objective is to remove k columns such that the sum over all rows of the maximum entry in each row is minimized. This combinatorial problem is closely related to bipartite network interdiction problem which can be applied to prioritize the border checkpoints in order to minimize the probability that an adversary can successfully cross the border. After introducing the matrix interdiction problem, we will prove the problem is NP-hard, and even NP-hard to approximate with an additive n{gamma} factor for a fixed constant {gamma}. We also present an algorithm for this problem that achieves a factor of (n-k) mUltiplicative approximation ratio.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Pan, Feng, Kasiviswanathan, Shiva. 2010-01-01. Matrix interdiction problem. https://doi.org/10.1155/2010%2F901587
Cite the original work for its findings. Save a collection to share your selection of sources.