Packing interdiction and partial covering problems

Michael Dinitz, Anupam Gupta

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 16th International Conference, IPCO 2013, Proceedings
Number of pages12
StatePublished - 2013
Event16th Conference on Integer Programming and Combinatorial Optimization, IPCO 2013 - Valparaiso, Chile
Duration: Mar 18 2013Mar 20 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7801 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference16th Conference on Integer Programming and Combinatorial Optimization, IPCO 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Packing interdiction and partial covering problems'. Together they form a unique fingerprint.

Cite this