Document Open Access Logo

Approximation Algorithms for Interdiction Problem with Packing Constraints

Authors Lin Chen, Xiaoyu Wu, Guochuan Zhang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2022.39.pdf
  • Filesize: 0.81 MB
  • 19 pages

Document Identifiers

Author Details

Lin Chen
  • Department of Computer Science, Texas Tech University, Lubbock, TX, USA
Xiaoyu Wu
  • School of Mathematical Sciences, Zhejiang University, Hangzhou, China
Guochuan Zhang
  • School of Computer Science, Zhejiang University, Hangzhou, China

Funding

  • Chen, Lin: NSF No. 2004096
  • Zhang, Guochuan: NSFC Key Program No. 12131003

Cite AsGet BibTex

Lin Chen, Xiaoyu Wu, and Guochuan Zhang. Approximation Algorithms for Interdiction Problem with Packing Constraints. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 39:1-39:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ICALP.2022.39

Abstract

We study a bilevel optimization problem which is a zero-sum Stackelberg game. In this problem, there are two players, a leader and a follower, who pick items from a common set. Both the leader and the follower have their own (multi-dimensional) budgets, respectively. Each item is associated with a profit, which is the same to the leader and the follower, and will consume the leader’s (follower’s) budget if it is selected by the leader (follower). The leader and the follower will select items in a sequential way: First, the leader selects items within the leader’s budget. Then the follower selects items from the remaining items within the follower’s budget. The goal of the leader is to minimize the maximum profit that the follower can obtain. Let s_A and s_B be the dimension of the leader’s and follower’s budget, respectively. A special case of our problem is the bilevel knapsack problem studied by Caprara et al. [SIAM Journal on Optimization, 2014], where s_A = s_B = 1. We consider the general problem and obtain an (s_B+ε)-approximation algorithm when s_A and s_B are both constant. In particular, if s_B = 1, our algorithm implies a PTAS for the bilevel knapsack problem, which is the first 𝒪(1)-approximation algorithm. We also complement our result by showing that there does not exist any (4/3-ε)-approximation algorithm even if s_A = 1 and s_B = 2. We also consider a variant of our problem with resource augmentation when s_A and s_B are both part of the input. We obtain an 𝒪(1)-approximation algorithm with 𝒪(1)-resource augmentation, that is, we give an algorithm that returns a solution which exceeds the given leader’s budget by 𝒪(1) times, and the objective value achieved by the solution is 𝒪(1) times the optimal objective value that respects the leader’s budget.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Bilevel Integer Programming
  • Interdiction Constraints
  • Knapsack

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Bo An, Fernando Ordóñez, Milind Tambe, Eric Shieh, Rong Yang, Craig Baldwin, Joseph DiRenzo III, Kathryn Moretti, Ben Maule, and Garrett Meyer. A deployed quantal response-based patrol planning system for the us coast guard. Interfaces, 43(5):400-420, 2013. Google Scholar
  2. Luce Brotcorne, Saïd Hanafi, and Raïd Mansi. One-level reformulation of the bilevel knapsack problem using dynamic programming. Discrete Optimization, 10(1):1-10, 2013. Google Scholar
  3. Carl Burch, Robert Carr, Sven Krumke, Madhav Marathe, Cynthia Phillips, and Eric Sundberg. A decomposition-based pseudoapproximation algorithm for network flow inhibition. In Network Interdiction and Stochastic Integer Programming, chapter 3, pages 51-68. Springer, 2003. Google Scholar
  4. Alberto Caprara, Margarida Carvalho, Andrea Lodi, and Gerhard J. Woeginger. A complexity and approximability study of the bilevel knapsack problem. In Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization, pages 98-109, 2013. Google Scholar
  5. Alberto Caprara, Hans Kellerer, Ulrich Pferschy, and David Pisinger. Approximation algorithms for knapsack problems with cardinality constraints. European Journal of Operational Research, 123(2):333-345, 2000. Google Scholar
  6. Margarida Carvalho, Andrea Lodi, and Patrice Marcotte. A polynomial algorithm for a continuous bilevel knapsack problem. Operations Research Letters, 46(2):185-188, 2018. Google Scholar
  7. Lin Chen, Xiaoyu Wu, and Guochuan Zhang. Approximation algorithms for interdiction problem with packing constraints. arXiv, 2022. Google Scholar
  8. Lin Chen and Guochuan Zhang. Approximation algorithms for a bi-level knapsack problem. Theoretical Computer Science, 497:1-12, 2013. Google Scholar
  9. Stephen R Chestnut and Rico Zenklusen. Hardness and approximation for network flow interdiction. Networks, 69(4):378-387, 2017. Google Scholar
  10. Stephen R. Chestnut and Rico Zenklusen. Interdicting structured combinatorial optimization problems with 0, 1-objectives. Mathematics of Operations Research, 42(1):144-166, 2017. Google Scholar
  11. Benoît Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of Operations Research, 153(1):235-256, 2007. Google Scholar
  12. Federico Della Croce and Rosario Scatamacchia. An exact approach for the bilevel knapsack problem with interdiction constraints and extensions. Mathematical Programming, 183(1):249-281, 2020. Google Scholar
  13. Stephan Dempe and Klaus Richter. Bilevel programming with knapsack constraints. Central European Journal of Operations Research, 8(2):93-108, 2000. Google Scholar
  14. Scott DeNegre. Interdiction and discrete bilevel linear programming. PhD thesis, Lehigh University, 2011. Google Scholar
  15. Michael Dinitz and Anupam Gupta. Packing interdiction and partial covering problems. In Proceedings of the 16th international conference on Integer Programming and Combinatorial Optimization, pages 157-168, 2013. Google Scholar
  16. Avinash Dixit. The role of investment in entry-deterrence. The economic journal, 90(357):95-106, 1980. Google Scholar
  17. Dennis Fischer and Gerhard J. Woeginger. A faster algorithm for the continuous bilevel knapsack problem. Operations Research Letters, 48(6):784-786, 2020. Google Scholar
  18. Matteo Fischetti, Ivana Ljubic, Michele Monaci, and Markus Sinnl. A new general-purpose algorithm for mixed-integer bilevel linear programs. Operations Research, 65(6):1615-1637, 2017. Google Scholar
  19. Matteo Fischetti, Ivana Ljubic, Michele Monaci, and Markus Sinnl. Interdiction games and monotonicity, with application to knapsack problems. INFORMS Journal on Computing, 31(2):390-410, 2019. Google Scholar
  20. Matteo Fischetti, Michele Monaci, and Markus Sinnl. A dynamic reformulation heuristic for generalized interdiction problems. European Journal of Operational Research, 267(1):40-51, 2018. Google Scholar
  21. Klaus Jansen. An eptas for scheduling jobs on uniform processors: using an milp relaxation with a constant number of integral variables. SIAM Journal on Discrete Mathematics, 24(2):457-485, 2010. Google Scholar
  22. Klaus Jansen. Parameterized approximation scheme for the multiple knapsack problem. SIAM Journal on Computing, 39(4):1392-1412, 2010. Google Scholar
  23. Robert G. Jeroslow. The polynomial hierarchy and a simple model for competitive analysis. Mathematical Programming, 32(2):146-164, 1985. Google Scholar
  24. Shiva Prasad Kasiviswanathan and Feng Pan. Matrix interdiction problem. In Proceedings of the 7th international conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, pages 219-231, 2010. Google Scholar
  25. Thomas Kleinert, Martine Labbé, Ivana Ljubic, and Martin Schmidt. A survey on mixed-integer programming techniques in bilevel optimization. EURO Journal on Computational Optimization, 2021. Google Scholar
  26. André Linhares and Chaitanya Swamy. Improved algorithms for mst and metric-tsp interdiction. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, pages 32:1-32:14, 2017. Google Scholar
  27. D. johnson) M. Garey. Computers and intractability: a guide to the theory of np-completeness. Siam Review, 24(1):90, 1982. Google Scholar
  28. Feng Pan and Aaron Schild. Interdiction problems on planar graphs. Discrete Applied Mathematics, 198:215-231, 2016. Google Scholar
  29. Praveen Paruchuri, Jonathan P Pearce, Janusz Marecki, Milind Tambe, Fernando Ordonez, and Sarit Kraus. Efficient algorithms to solve bayesian stackelberg games for security applications. In Proceedings of the 23th AAAI Conference on Artificial Intelligence, pages 1559-1562, 2008. Google Scholar
  30. Ulrich Pferschy, Gaia Nicosia, and Andrea Pacifici. A stackelberg knapsack game with weight control. Theoretical Computer Science, 799:149-159, 2019. Google Scholar
  31. Ulrich Pferschy, Gaia Nicosia, Andrea Pacifici, and Joachim Schauer. On the stackelberg knapsack game. European Journal of Operational Research, 291(1):18-31, 2021. Google Scholar
  32. Cynthia A. Phillips. The network inhibition problem. In Proceedings of the 25th annual ACM symposium on Theory of computing, pages 776-785, 1993. Google Scholar
  33. James Pita, Manish Jain, Janusz Marecki, Fernando Ordóñez, Christopher Portway, Milind Tambe, Craig Western, Praveen Paruchuri, and Sarit Kraus. Deployed armor protection: the application of a game theoretic model for security at the los angeles international airport. In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, pages 125-132, 2008. Google Scholar
  34. Xian Qiu and Walter Kern. Improved approximation algorithms for a bilevel knapsack problem. Theoretical Computer Science, 595:120-129, 2015. Google Scholar
  35. Yen Tang, Jean-Philippe P. Richard, and J. Cole Smith. A class of algorithms for mixed-integer bilevel min-max optimization. Journal of Global Optimization, 66(2):225-262, 2016. Google Scholar
  36. Rico Zenklusen. Matching interdiction. Discrete Applied Mathematics, 158(15):1676-1690, 2010. Google Scholar
  37. Rico Zenklusen. Network flow interdiction on planar graphs. Discrete Applied Mathematics, 158(13):1441-1455, 2010. Google Scholar
  38. Rico Zenklusen. Connectivity interdiction. Operations Research Letters, 42(6-7):450-454, 2014. Google Scholar
  39. Rico Zenklusen. An o(1)-approximation for minimum spanning tree interdiction. In Proceedings of the 56th Annual Symposium on Foundations of Computer Science, pages 709-728, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact