Interdiction problems and 2-person sequential games: beyond NP-completeness

Abstract

In the Knapsack Problem (KP), a decision maker wants to select items of value V or more to put into a knapsack subject to a weight limit.  In the Interdiction Knapsack Problem (IKP), an adversary can block K items from being selected.  The adversary’s goal is to prevent the decision maker from achieving a value of V. The IKP is a sequential game with an initial move by the adversary followed by a move from the decision maker. The Knapsack Problem is NP-complete. The IKP is one level harder than NP-complete. 

We have proved a meta-theorem which establishes that the Interdiction Traveling Salesman Problem, the Interdiction Set Packing Problem, the Interdiction Set Cover Problem, and hundreds of other interdiction problems are all one level harder than NP-complete.  We have also established meta-theorems showing that hundreds of min max regret problems are one level harder than NP-complete.  We discuss our meta-theorems and relate them to the complexity of 2-person sequential games.

This talk does not assume a knowledge of complexity other than an understanding of NP-completeness.

This work is joint with Christoph Grüne, Berit Johannes, and Lasse Wulf.

Speaker Bio

James Orlin is the E. Pennell Brooks (1917) Professor of Operations Research at the MIT Sloan School.  He is best known for his research on obtaining faster algorithms for problems in network and combinatorial optimization and for his text with Ravi Ahuja and Tom Magnanti entitled Network Flows: Theory, Algorithms, and Applications. 

He has won various awards for his co-authored publications: including the 1993 Lanchester Prize for the best publication in O.R., the 2016 ACM SIGecom Test of Time Award, for a paper published between 10 and 25 years ago that has had “significant impact on research or applications that exemplify the interplay of economics and computation,” and the 2020 Khachyian prize for lifetime achievements in the area of optimization.  He is also a MacVicar fellow, an honor that is awarded at MIT to faculty for their “outstanding contributions to undergraduate education, and for their exceptional teaching, mentoring, and educational innovation.”