TY - GEN

T1 - Packing interdiction and partial covering problems

AU - Dinitz, Michael

AU - Gupta, Anupam

PY - 2013

Y1 - 2013

N2 - In the Packing Interdiction problem we are given a packing LP together with a separate interdiction cost for each LP variable and a global interdiction budget. Our goal is to harm the LP: which variables should we forbid the LP from using (subject to forbidding variables of total interdiction cost at most the budget) in order to minimize the value of the resulting LP? Interdiction problems on graphs (interdicting the maximum flow, the shortest path, the minimum spanning tree, etc.) have been considered before; here we initiate a study of interdicting packing linear programs. Zenklusen showed that matching interdiction, a special case, is NP-hard and gave a 4-approximation for unit edge weights. We obtain an constant-factor approximation to the matching interdiction problem without the unit weight assumption. This is a corollary of our main result, an O(log q · min {q, logk})-approximation to Packing Interdiction where q is the row-sparsity of the packing LP and k is the column-sparsity.

AB - In the Packing Interdiction problem we are given a packing LP together with a separate interdiction cost for each LP variable and a global interdiction budget. Our goal is to harm the LP: which variables should we forbid the LP from using (subject to forbidding variables of total interdiction cost at most the budget) in order to minimize the value of the resulting LP? Interdiction problems on graphs (interdicting the maximum flow, the shortest path, the minimum spanning tree, etc.) have been considered before; here we initiate a study of interdicting packing linear programs. Zenklusen showed that matching interdiction, a special case, is NP-hard and gave a 4-approximation for unit edge weights. We obtain an constant-factor approximation to the matching interdiction problem without the unit weight assumption. This is a corollary of our main result, an O(log q · min {q, logk})-approximation to Packing Interdiction where q is the row-sparsity of the packing LP and k is the column-sparsity.

UR - http://www.scopus.com/inward/record.url?scp=84875520379&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84875520379&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-36694-9_14

DO - 10.1007/978-3-642-36694-9_14

M3 - Conference contribution

AN - SCOPUS:84875520379

SN - 9783642366932

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 157

EP - 168

BT - Integer Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Proceedings

T2 - 16th Conference on Integer Programming and Combinatorial Optimization, IPCO 2013

Y2 - 18 March 2013 through 20 March 2013

ER -