On a Class of Interdiction Problems with Partition Matroids: Complexity and Polynomial-Time Algorithms

References

• Arora S, Barak B (2009) Computational Complexity: A Modern Approach (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Bazgan C, Toubaline S, Vanderpooten D (2012) Efficient determination of the k most vital edges for the minimum spanning tree problem. Comput. Oper. Res. 39(11):2888–2898.Crossref, Google Scholar
• Beheshti B, Prokopyev OA, Pasiliao EL (2016) Exact solution approaches for bilevel assignment problems. Comput. Optim. Appl. 64(1):215–242.Crossref, Google Scholar
• Bellman R (1958) On a routing problem. Quart. Appl. Math. 16(1):87–90.Crossref, Google Scholar
• Böhnlein T, Schaudt O (2020) On the complexity of Stackelberg matroid pricing problems. Gąsieniec L, Klasing R, Radzik T, eds. Combin. Algorithms 31st Internat. Workshop IWOCA 2020 Proc. (Springer, Cham, Switzerland), 83–96.Google Scholar
• Briest P, Hoefer M, Krysta P (2012) Stackelberg network pricing games. Algorithmica 62(3):733–753.Crossref, Google Scholar
• Buchheim C, Henke D, Hommelsheim F (2022) On the complexity of the bilevel minimum spanning tree problem. Networks 80(3):338–355.Crossref, Google Scholar
• Caprara A, Carvalho M, Lodi A, Woeginger GJ (2013) A complexity and approximability study of the bilevel knapsack problem. Goemans M, Correa J, eds. Integer Programming Combin. Optim. IPCO 2013 (Springer, Berlin), 98–109.Google Scholar
• Caprara A, Carvalho M, Lodi A, Woeginger GJ (2014) A study on the computational complexity of the bilevel knapsack problem. SIAM J. Optim. 24(2):823–838.Crossref, Google Scholar
• Caprara A, Carvalho M, Lodi A, Woeginger GJ (2016) Bilevel knapsack with interdiction constraints. INFORMS J. Comput. 28(2):319–333.Link, Google Scholar
• Chen L, Wu X, Zhang G (2022) Approximation algorithms for interdiction problem with packing constraints. Preprint, submitted April 22, https://arxiv.org/abs/2204.11106.Google Scholar
• Chestnut SR, Zenklusen R (2017) Interdicting structured combinatorial optimization problems with {0, 1}-objectives. Math. Oper. Res. 42(1):144–166.Link, Google Scholar
• DeNegre S (2011) Interdiction and discrete bilevel linear programming. PhD dissertation, Lehigh University, Bethlehem, PA.Google Scholar
• Dinitz M, Gupta A (2013) Packing interdiction and partial covering problems. Goemans M, Correa J, eds. Integer Programming Combin. Optim. IPCO 2013 (Springer, Berlin), 157–168.Google Scholar
• Downey RG, Fellows MR (2012) Parameterized Complexity (Springer Science & Business Media, Berlin).Google Scholar
• Edmonds J (1971) Matroids and the greedy algorithm. Math. Programming 1(1):127–136.Crossref, Google Scholar
• Edmonds J (2003) Submodular functions, matroids, and certain polyhedra. Jünger M, Reinelt G, Rinaldi G, eds. Combinatorial Optimization—Eureka, You Shrink! (Springer, Berlin), 11–26.Crossref, Google Scholar
• Fischetti M, Ljubić I, Monaci M, Sinnl M (2019) Interdiction games and monotonicity, with application to knapsack problems. INFORMS J. Comput. 31(2):390–410.Link, Google Scholar
• Fisher ML, Nemhauser GL, Wolsey LA (1978) An analysis of approximations for maximizing submodular set functions–II. Math. Programming Stud. 8:73–87.Crossref, Google Scholar
• Frederickson GN, Solis-Oba R (1997) Efficient algorithms for robustness in matroid optimization. SODA ‘97 Proc. 8th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 659–668.Google Scholar
• Frederickson GN, Solis-Oba R (1999) Increasing the weight of minimum spanning trees. J. Algorithms 33(2):244–266.Crossref, Google Scholar
• Frederickson GN, Solis-Oba R (2006) Efficient algorithms for robustness in resource allocation and scheduling problems. Theoret. Comput. Sci. 352(1–3):250–265.Crossref, Google Scholar
• Fulkerson DR, Harding GC (1977) Maximizing the minimum source-sink path subject to a budget constraint. Math. Programming 13(1):116–118.Crossref, Google Scholar
• Garey MR, Johnson DS (2002) Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York).Google Scholar
• Gassner E, Klinz B (2009) The computational complexity of bilevel assignment problems. 4OR 7(4):379–394.Crossref, Google Scholar
• Hausbrandt N, Bachtler O, Ruzika S, Schäfer LE (2024) Parametric matroid interdiction. Discrete Optim. 51:100823.Crossref, Google Scholar
• Israeli E, Wood RK (2002) Shortest-path network interdiction. Networks 40(2):97–111.Crossref, Google Scholar
• Iwata S, Nagano K (2009) Submodular function minimization under covering constraints. 2009 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, New York), 671–680.Google Scholar
• Iwata S, Fleischer L, Fujishige S (2001) A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4):761–777.Crossref, Google Scholar
• Jensen PM, Korte B (1982) Complexity of matroid property algorithms. SIAM J. Comput. 11(1):184–190.Crossref, Google Scholar
• Jeroslow RG (1985) The polynomial hierarchy and a simple model for competitive analysis. Math. Programming 32(2):146–164.Crossref, Google Scholar
• Kamiyama N (2018) A note on submodular function minimization with covering type linear constraints. Algorithmica 80:2957–2971.Crossref, Google Scholar
• Kleinert T, Labbé M, Ljubić I, Schmidt M (2021) A survey on mixed-integer programming techniques in bilevel optimization. EURO J. Comput. Optim. 9:100007.Crossref, Google Scholar
• Lunday BJ, Sherali HD (2012a) Minimizing the maximum network flow: Models and algorithms with resource synergy considerations. J. Oper. Res. Soc. 63(12):1693–1707.Crossref, Google Scholar
• Lunday BJ, Sherali HD (2012b) Network interdiction to minimize the maximum probability of evasion with synergy between applied resources. Ann. Oper. Res. 196:411–442.Crossref, Google Scholar
• McCormick ST (2005) Submodular function minimization. Aardal K, Nemhauser GL, Weismantel R, eds. Discrete Optimization. Handbooks in Operations Research and Management Science, vol. 12 (Elsevier, Amsterdam), 321–391.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions – I. Math. Programming 14(1):265–294.Crossref, Google Scholar
• Orlin JB, Punnen AP, Schulz AS (2004) Approximate local search in combinatorial optimization. SIAM J. Comput. 33(5):1201–1214.Crossref, Google Scholar
• Oxley J (2011) Matroid Theory. Oxford Graduate Texts in Mathematics, vol. 21, 2nd ed. (Oxford University Press, Oxford, UK).Google Scholar
• Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80(2):346–355.Crossref, Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24 (Springer, Berlin).Google Scholar
• Shi X, Prokopyev OA, Ralphs TK (2023) Mixed integer bilevel optimization with a k-optimal follower: A hierarchy of bounds. Math. Programming Comput. 15(1):1–51.Crossref, Google Scholar
• Shi X, Zeng B, Prokopyev OA (2019) On bilevel minimum and bottleneck spanning tree problems. Networks 74(3):251–273.Crossref, Google Scholar
• Smith JC, Song Y (2020) A survey of network interdiction models and algorithms. Eur. J. Oper. Res. 283(3):797–811.Crossref, Google Scholar
• Smith JC, Prince M, Geunes J (2013) Modern network interdiction problems and algorithms. Pardalos PM, Du D-Z, Graham RL, eds. Handbook of Combinatorial Optimization (Springer, New York), 1949–1987.Crossref, Google Scholar
• Wei N, Walteros JL, Pajouh FM (2021) Integer programming formulations for minimum spanning tree interdiction. INFORMS J. Comput. 33(4):1461–1480.Abstract, Google Scholar
• Wood RK (2010) Bilevel network interdiction models: Formulations and solutions. Cochran JJ, Cox LA Jr, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia of Operations Research and Management Science (John Wiley & Sons, Inc., Hoboken, NJ), 1–11.Google Scholar
• Yang J, Shi X, Prokopyev OA (2023) Exact solution approaches for a class of bilevel fractional programs. Optim. Lett. 17(1):191–210.Crossref, Google Scholar
• Zenklusen R (2010) Matching interdiction. Discrete Appl. Math. 158(15):1676–1690.Crossref, Google Scholar
• Zenklusen R (2015) An O(1)-approximation for minimum spanning tree interdiction. 2015 IEEE 56th Annual Sympos. Foundations Comput. Sci. (IEEE, New York), 709–728.Google Scholar
• Zenklusen R, Ries B, Picouleau C, De Werra D, Costa M-C, Bentz C (2009) Blockers and transversals. Discrete Math. 309(13):4306–4314.Crossref, Google Scholar