{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:13:10Z","timestamp":1784110390964,"version":"3.55.0"},"publisher-location":"Singapore","reference-count":32,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819610891","type":"print"},{"value":"9789819610907","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-1090-7_3","type":"book-chapter","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T16:32:31Z","timestamp":1741105951000},"page":"29-41","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Extensions of\u00a0Min-k-Union$$^\\star $$"],"prefix":"10.1007","author":[{"given":"Hua","family":"Chen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lin","family":"Chen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shenghao","family":"Ye","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guochuan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,3,5]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Bhaskara, A., Charikar, M., Chlamt\u00e1\u010d, E., Feige, U., Vijayaraghavan, A.: Detecting high log-densities: an $${O}(n^{1\/4})$$ approximation for densest $$k$$-subgraph. In: Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pp. 201\u2013210 (2010)","DOI":"10.1145\/1806689.1806719"},{"key":"3_CR2","series-title":"Operations Research\/Computer Science Interfaces Series","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/0-306-48109-X_3","volume-title":"Network Interdiction and Stochastic Integer Programming","author":"C Burch","year":"2003","unstructured":"Burch, C., Carr, R., Krumke, S., Marathe, M., Phillips, C., Sundberg, E.: A decomposition-based pseudoapproximation algorithm for network flow inhibition. In: Woodruff, D.L. (ed.) Network Interdiction and Stochastic Integer Programming. Operations Research\/Computer Science Interfaces Series, vol. 22, pp. 51\u201368. Springer, Boston (2003). https:\/\/doi.org\/10.1007\/0-306-48109-X_3"},{"key":"3_CR3","unstructured":"Chen, L., Wu, X., Zhang, G.: Approximation algorithms for interdiction problem with packing constraints. In: Proceedings of the 49th International Colloquium on Automata, Languages, and Programming (ICALP). LIPIcs, vol.\u00a0229, pp. 39:1\u201339:19 (2022)"},{"issue":"4","key":"3_CR4","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1002\/net.21739","volume":"69","author":"SR Chestnut","year":"2017","unstructured":"Chestnut, S.R., Zenklusen, R.: Hardness and approximation for network flow interdiction. Networks 69(4), 378\u2013387 (2017)","journal-title":"Networks"},{"issue":"1","key":"3_CR5","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1287\/moor.2016.0798","volume":"42","author":"SR Chestnut","year":"2017","unstructured":"Chestnut, S.R., Zenklusen, R.: Interdicting structured combinatorial optimization problems with $$\\{$$0, 1$$\\}$$-objectives. Math. Oper. Res. 42(1), 144\u2013166 (2017)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"3_CR6","doi-asserted-by":"publisher","first-page":"1458","DOI":"10.1137\/16M1096402","volume":"32","author":"E Chlamt\u00e1\u010d","year":"2018","unstructured":"Chlamt\u00e1\u010d, E., Dinitz, M., Konrad, C., Kortsarz, G., Rabanca, G.: The densest $$k$$-subhypergraph problem. SIAM J. Discret. Math. 32(2), 1458\u20131477 (2018)","journal-title":"SIAM J. Discret. Math."},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Chlamt\u00e1\u010d, E., Dinitz, M., Krauthgamer, R.: Everywhere-sparse spanners via dense subgraphs. In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 758\u2013767 (2012)","DOI":"10.1109\/FOCS.2012.61"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Chlamt\u00e1\u010d, E., Dinitz, M., Makarychev, Y.: Minimizing the union: tight approximations for small set bipartite vertex expansion. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 881\u2013899 (2017)","DOI":"10.1137\/1.9781611974782.56"},{"key":"3_CR9","unstructured":"DeNegre, S.: Interdiction and Discrete Bilevel Linear Programming. Lehigh University (2011)"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Dinitz, M., Gupta, A.: Packing interdiction and partial covering problems. In: Proceedings of the 16th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 157\u2013168 (2013)","DOI":"10.1007\/978-3-642-36694-9_14"},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. In: Combinatorial Optimization\u2014Eureka, You Shrink! Papers Dedicated to Jack Edmonds 5th International Workshop Aussois, France, 5\u20139 March 2001 Revised Papers, pp. 11\u201326 (2003)","DOI":"10.1007\/3-540-36478-1_2"},{"issue":"4","key":"3_CR12","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U Feige","year":"2001","unstructured":"Feige, U., Peleg, D., Kortsarz, G.: The dense $$k$$-subgraph problem. Algorithmica 29, 410\u2013421 (2001)","journal-title":"Algorithmica"},{"key":"3_CR14","unstructured":"Fujishige, S.: Submodular Functions and Optimization. Elsevier (2005)"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"3_CR16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/978-3-642-78240-4"},{"issue":"4","key":"3_CR17","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4), 761\u2013777 (2001)","journal-title":"J. ACM"},{"key":"3_CR18","unstructured":"Kortsarz, G., Peleg, D.: On Choosing a Dense Subgraph. IEEE (1993)"},{"key":"3_CR19","unstructured":"Linhares, A., Swamy, C.: Improved algorithms for MST and metric-TSP interdiction. In: Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP). LIPIcs, vol.\u00a080, pp. 32:1\u201332:14 (2017)"},{"key":"3_CR20","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. Mathematical Programming The State of the Art: Bonn 1982, pp. 235\u2013257 (1983)","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Manurangsi, P.: Almost-polynomial ratio ETH-hardness of approximating densest $$k$$-subgraph. In: Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), pp. 954\u2013961 (2017)","DOI":"10.1145\/3055399.3055412"},{"key":"3_CR22","unstructured":"Naamad, Y.: Hardness from densest subgraph conjectures. Ph.D. thesis, Princeton University (2017)"},{"issue":"6","key":"3_CR23","doi-asserted-by":"publisher","first-page":"1351","DOI":"10.1007\/s00493-019-3900-1","volume":"39","author":"M N\u00e4gele","year":"2019","unstructured":"N\u00e4gele, M., Sudakov, B., Zenklusen, R.: Submodular minimization under congruency constraints. Combinatorica 39(6), 1351\u20131386 (2019)","journal-title":"Combinatorica"},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions\u2013I. Math. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"issue":"2","key":"3_CR25","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory Ser. B. 80(2), 346\u2013355 (2000)","journal-title":"J. Comb. Theory Ser. B."},{"key":"3_CR26","volume-title":"The Theory of the Market Economy","author":"HV Stackelberg","year":"1952","unstructured":"Stackelberg, H.V.: The Theory of the Market Economy. Oxford University Press, New York (1952)"},{"issue":"6","key":"3_CR27","doi-asserted-by":"publisher","first-page":"1715","DOI":"10.1137\/100783352","volume":"40","author":"Z Svitkina","year":"2011","unstructured":"Svitkina, Z., Fleischer, L.: Submodular approximation: sampling-based algorithms and lower bounds. SIAM J. Comput. 40(6), 1715\u20131737 (2011)","journal-title":"SIAM J. Comput."},{"key":"3_CR28","volume-title":"Supermodularity and Complementarity","author":"DM Topkis","year":"1998","unstructured":"Topkis, D.M.: Supermodularity and Complementarity. Princeton University Press, Princeton (1998)"},{"key":"3_CR29","doi-asserted-by":"crossref","unstructured":"Weninger, N., Fukasawa, R.: A fast combinatorial algorithm for the bilevel knapsack problem with interdiction constraints. In: Proceedings of the 24th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 438\u2013452 (2023)","DOI":"10.1007\/978-3-031-32726-1_31"},{"issue":"15","key":"3_CR30","doi-asserted-by":"publisher","first-page":"1676","DOI":"10.1016\/j.dam.2010.06.006","volume":"158","author":"R Zenklusen","year":"2010","unstructured":"Zenklusen, R.: Matching interdiction. Discret. Appl. Math. 158(15), 1676\u20131690 (2010)","journal-title":"Discret. Appl. Math."},{"issue":"6\u20137","key":"3_CR31","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1016\/j.orl.2014.07.010","volume":"42","author":"R Zenklusen","year":"2014","unstructured":"Zenklusen, R.: Connectivity interdiction. Oper. Res. Lett. 42(6\u20137), 450\u2013454 (2014)","journal-title":"Oper. Res. Lett."},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"Zenklusen, R.: An $$o(1)$$-approximation for minimum spanning tree interdiction. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pp. 709\u2013728 (2015)","DOI":"10.1109\/FOCS.2015.49"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-1090-7_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T06:55:02Z","timestamp":1757141702000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-1090-7_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819610891","9789819610907"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-1090-7_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"5 March 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/anl.sjtu.edu.cn\/cocoon2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}