{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:23:08Z","timestamp":1772119388955,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,10,10]],"date-time":"2023-10-10T00:00:00Z","timestamp":1696896000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,10]],"date-time":"2023-10-10T00:00:00Z","timestamp":1696896000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004721","name":"The University of Tokyo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004721","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    In this paper, we study the following robust optimization problem. Given a set family representing feasibility and candidate objective functions, we choose a feasible set, and then an adversary chooses one objective function, knowing our choice. The goal is to find a randomized strategy (i.e., a probability distribution over the feasible sets) that maximizes the expected objective value in the worst case. This problem is fundamental in wide areas such as artificial intelligence, machine learning, game theory, and optimization. To solve the problem, we provide a general framework based on the dual linear programming problem. In the framework, we utilize the ellipsoid algorithm with the approximate separation algorithm. We prove that there exists an\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\alpha $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03b1<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -approximation algorithm for our robust optimization problem if there exists an\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\alpha $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03b1<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    -approximation algorithm for finding a (deterministic) feasible set that maximizes a nonnegative linear combination of the candidate objective functions. Using our result, we provide approximation algorithms for the max\u2013min fair randomized allocation problem and the maximum cardinality robustness problem with a knapsack constraint.\n                  <\/jats:p>","DOI":"10.1007\/s00453-023-01175-3","type":"journal-article","created":{"date-parts":[[2023,10,10]],"date-time":"2023-10-10T10:03:22Z","timestamp":1696932202000},"page":"566-584","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Randomized Strategies for Robust Combinatorial Optimization with Approximate Separation"],"prefix":"10.1007","volume":"86","author":[{"given":"Yasushi","family":"Kawase","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanna","family":"Sumita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,10]]},"reference":[{"issue":"2","key":"1175_CR1","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1016\/j.ejor.2008.09.012","volume":"197","author":"H Aissi","year":"2009","unstructured":"Aissi, H., Bazgan, C., Vanderpooten, D.: Min\u2013max and min\u2013max regret versions of combinatorial optimization problems: a survey. EJOR 197(2), 427\u2013438 (2009)","journal-title":"EJOR"},{"key":"1175_CR2","doi-asserted-by":"publisher","DOI":"10.2307\/j.ctvcm4gc3","volume-title":"Microeconomics: Behavior, Institutions, and Evolution","author":"S Bowles","year":"2009","unstructured":"Bowles, S.: Microeconomics: Behavior, Institutions, and Evolution. Princeton University Press, Princeton (2009)"},{"key":"1175_CR3","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a submodular set function subject to a matroid constraint. In: IPCO, vol. 7, pp. 182\u2013196. Springer (2007)","DOI":"10.1007\/978-3-540-72792-7_15"},{"issue":"2","key":"1175_CR4","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0377-2217(99)00261-1","volume":"123","author":"A Caprara","year":"2000","unstructured":"Caprara, A., Kellerer, H., Pferschy, U., Pisinger, D.: Approximation algorithms for knapsack problems with cardinality constraints. EJOR 123(2), 333\u2013345 (2000)","journal-title":"EJOR"},{"key":"1175_CR5","unstructured":"Chen, R.S., Lucier, B., Singer, Y., Syrgkanis, V.: Robust optimization for non-convex objectives. In: Proceedings of the NIPS, pp. 4708\u20134717 (2017)"},{"key":"1175_CR6","doi-asserted-by":"crossref","unstructured":"Filmus, Y., Ward, J.: A tight combinatorial algorithm for submodular maximization subject to a matroid constraint. In: Proceedings of the FOCS, 659\u2013668. IEEE (2012)","DOI":"10.1109\/FOCS.2012.55"},{"issue":"1\u20132","key":"1175_CR7","first-page":"79","volume":"29","author":"Y Freund","year":"1999","unstructured":"Freund, Y., Schapire, R.E.: Adaptive game playing using multiplicative weights. GEB 29(1\u20132), 79\u2013103 (1999)","journal-title":"GEB"},{"key":"1175_CR8","volume-title":"Submodular Functions and Optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization, vol. 58. Elsevier, Amsterdam (2005)"},{"key":"1175_CR9","first-page":"1234","volume":"27","author":"R Fujita","year":"2013","unstructured":"Fujita, R., Kobayashi, Y., Makino, K.: Robust Matchings and Matroid Intersections 27, 1234\u20131256 (2013)","journal-title":"Robust Matchings and Matroid Intersections"},{"key":"1175_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"key":"1175_CR11","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"2012","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, vol. 2. Springer, Berlin (2012)"},{"issue":"4","key":"1175_CR12","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1137\/S0895480198332156","volume":"15","author":"R Hassin","year":"2002","unstructured":"Hassin, R., Rubinstein, S.: Robust matchings. SIDMA 15(4), 530\u2013537 (2002)","journal-title":"SIDMA"},{"issue":"1\u20133","key":"1175_CR13","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0304-3975(02)00829-0","volume":"302","author":"K Jansen","year":"2003","unstructured":"Jansen, K.: Approximate strong separation with application in fractional graph coloring and preemptive scheduling. Theor. Comput. Sci. 302(1\u20133), 239\u2013256 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"1175_CR14","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1137\/120899480","volume":"27","author":"N Kakimura","year":"2013","unstructured":"Kakimura, N., Makino, K.: Robust independence systems. SIDMA 27(3), 1257\u20131273 (2013)","journal-title":"SIDMA"},{"issue":"3","key":"1175_CR15","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/s13160-012-0075-z","volume":"29","author":"N Kakimura","year":"2012","unstructured":"Kakimura, N., Makino, K., Seimi, K.: Computing knapsack solutions with cardinality robustness. Jpn. J. Ind. Appl. Math. 29(3), 469\u2013483 (2012)","journal-title":"Jpn. J. Ind. Appl. Math."},{"key":"1175_CR16","unstructured":"Kale, S.: Efficient algorithms using the multiplicative weights update method. Ph.D. thesis, Princeton University (2007)"},{"key":"1175_CR17","first-page":"113","volume-title":"Robust Discrete Optimization Under Discrete and Interval Uncertainty: A Survey","author":"A Kasperski","year":"2016","unstructured":"Kasperski, A., Zieli\u0144ski, P.: Robust Discrete Optimization Under Discrete and Interval Uncertainty: A Survey, pp. 113\u2013143. Springer, Berlin (2016)"},{"key":"1175_CR18","doi-asserted-by":"crossref","unstructured":"Kawase, Y., Sumita, H.: Randomized strategies for robust combinatorial optimization. In: Proceedings of the AAAI (2019)","DOI":"10.1609\/aaai.v33i01.33017876"},{"key":"1175_CR19","doi-asserted-by":"crossref","unstructured":"Kawase, Y., Sumita, H.: On the max\u2013min fair stochastic allocation of indivisible goods. In: Proceedings of the AAAI (2020)","DOI":"10.1609\/aaai.v34i02.5580"},{"key":"1175_CR20","doi-asserted-by":"crossref","unstructured":"Kawase, Y., Miyauchi, A., Sumita, H.: Stochastic solutions for dense subgraph discovery in multilayer networks. In: Proceedings of the WSDM, pp. 886\u2013894 (2023)","DOI":"10.1145\/3539597.3570444"},{"key":"1175_CR21","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1016\/S0377-2217(99)00157-5","volume":"120","author":"H Kellerer","year":"2000","unstructured":"Kellerer, H., Mansini, R., Speranza, M.G.: Two linear approximation algorithms for the subset-sum problem. EJOR 120, 289\u2013296 (2000)","journal-title":"EJOR"},{"issue":"1","key":"1175_CR22","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/0041-5553(80)90061-0","volume":"20","author":"L Khachiyan","year":"1980","unstructured":"Khachiyan, L.: Polynomial algorithms in linear programming. USSR Comput. Math. Math. Phys. 20(1), 53\u201372 (1980)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"1175_CR23","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2016.12.019","volume":"699","author":"Y Kobayashi","year":"2016","unstructured":"Kobayashi, Y., Takazawa, K.: Randomized strategies for cardinality robustness in the knapsack problem. Theor. Comput. Sci. 699, 53\u201362 (2016)","journal-title":"Theor. Comput. Sci."},{"key":"1175_CR24","doi-asserted-by":"crossref","unstructured":"Krause, A., Golovin, D.: Submodular function maximization. In: Tractability: Practical Approaches to Hard Problems (to appear). Cambridge University Press, London (2014)","DOI":"10.1017\/CBO9781139177801.004"},{"key":"1175_CR25","first-page":"2761","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause, A., McMahan, H.B., Guestrin, C., Gupta, A.: Robust submodular observation selection. J. Mach. Learn. Res. 9, 2761\u20132801 (2008)","journal-title":"J. Mach. Learn. Res."},{"key":"1175_CR26","unstructured":"Krause, A., Roper, A., Golovin, D.: Randomized sensing in adversarial environments. In: Proceedings of the IJCAI, vol. 22, pp. 2133\u20132139 (2011)"},{"issue":"4","key":"1175_CR27","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1287\/moor.1100.0463","volume":"35","author":"J Lee","year":"2010","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4), 795\u2013806 (2010)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"1175_CR28","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1287\/moor.2017.0878","volume":"43","author":"J Matuschke","year":"2018","unstructured":"Matuschke, J., Skutella, M., Soto, J.A.: Robust randomized matchings. Math. Oper. Res. 43(2), 675\u2013692 (2018). https:\/\/doi.org\/10.1287\/moor.2017.0878","journal-title":"Math. Oper. Res."},{"key":"1175_CR29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511800481","volume-title":"Algorithmic Game Theory","author":"N Nisan","year":"2007","unstructured":"Nisan, N., Roughgarden, T., Tardos, \u00c9., Vazirani, V.V.: Algorithmic Game Theory. Cambridge University Press, London (2007)"},{"key":"1175_CR30","doi-asserted-by":"crossref","unstructured":"Orlin, J.B., Schulz, A.S., Udwani, R.: Robust monotone submodular function maximization. In: Proceedings of the IPCO, pp. 312\u2013324. Springer (2016)","DOI":"10.1007\/978-3-319-33461-5_26"},{"key":"1175_CR31","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics. Springer, Berlin (2003)"},{"issue":"1","key":"1175_CR32","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Let. 32(1), 41\u201343 (2004)","journal-title":"Oper. Res. Let."},{"key":"1175_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511973031","volume-title":"Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned","author":"M Tambe","year":"2011","unstructured":"Tambe, M.: Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned. Cambridge University Press, London (2011)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01175-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01175-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01175-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,24]],"date-time":"2024-01-24T04:10:31Z","timestamp":1706069431000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01175-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,10]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["1175"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01175-3","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2679599\/v1","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,10]]},"assertion":[{"value":"10 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 October 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}