{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:16:38Z","timestamp":1750306598039,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,11,16]],"date-time":"2015-11-16T00:00:00Z","timestamp":1447632000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-0448095, CCF-0729022, CCF-0728841 and CCF-1218382"],"award-info":[{"award-number":["CCF-0448095, CCF-0729022, CCF-0728841 and CCF-1218382"]}]},{"name":"Alfred P. Sloan Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2016,2,8]]},"abstract":"<jats:p>\n            Consider the following problem: given a set system (\n            <jats:italic>U<\/jats:italic>\n            , \u03a9) and an edge-weighted graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>U<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) on the same universe\n            <jats:italic>U<\/jats:italic>\n            , find the set\n            <jats:italic>A<\/jats:italic>\n            \u2208 \u03a9 such that the Steiner tree cost with terminals\n            <jats:italic>A<\/jats:italic>\n            is as large as possible\u2014\u201cwhich set in \u03a9 is the most difficult to connect up?\u201d This is an example of a\n            <jats:italic>max-min problem<\/jats:italic>\n            : find the set\n            <jats:italic>A<\/jats:italic>\n            \u2208 \u03a9 such that the value of some minimization (covering) problem is as large as possible.\n          <\/jats:p>\n          <jats:p>\n            In this article, we show that for certain covering problems that admit good deterministic online algorithms, we can give good algorithms for max-min optimization when the set system \u03a9 is given by a\n            <jats:italic>p<\/jats:italic>\n            -system or knapsack constraints or both. This result is similar to results for constrained maximization of submodular functions. Although many natural covering problems are not even approximately submodular, we show that one can use properties of the online algorithm as a surrogate for submodularity.\n          <\/jats:p>\n          <jats:p>\n            Moreover, we give stronger connections between max-min optimization and two-stage robust optimization, and hence give improved algorithms for robust versions of various covering problems, for cases where the uncertainty sets are given by\n            <jats:italic>p<\/jats:italic>\n            -systems and knapsack constraints.\n          <\/jats:p>","DOI":"10.1145\/2746226","type":"journal-article","created":{"date-parts":[[2015,11,18]],"date-time":"2015-11-18T13:42:28Z","timestamp":1447854148000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets"],"prefix":"10.1145","volume":"12","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}]}],"member":"320","published-online":{"date-parts":[[2015,11,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198522"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/060661946"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"A. Ben-Tal L.El Ghaoui and A. Nemirovski. 2009. Robust Optimization. Princeton University Press.  A. Ben-Tal L.El Ghaoui and A. Nemirovski. 2009. Robust Optimization. Princeton University Press.","DOI":"10.1515\/9781400831050"},{"key":"e_1_2_1_5_1","first-page":"178","article-title":"A d\/2 approximation for maximum weight independent set in d-claw free graphs","volume":"7","author":"Berman Piotr","year":"2000","unstructured":"Piotr Berman . 2000 . A d\/2 approximation for maximum weight independent set in d-claw free graphs . Nordic J. Comput. 7 , 3 (2000), 178 -- 184 . Piotr Berman. 2000. A d\/2 approximation for maximum weight independent set in d-claw free graphs. Nordic J. Comput. 7, 3 (2000), 178--184.","journal-title":"Nordic J. Comput."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258618"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/080734510"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700382820"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.42"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.011"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72792-7_33"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90053-5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793243016"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_16"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0705-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1940179.1940200"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777419"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0402008"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404033"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1361192.1361201"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 7th South Eastern Conference on Combinatorics, Graph Theory and Computing. 341--350","author":"Jenkyns T. A.","year":"1976","unstructured":"T. A. Jenkyns . 1976 . The efficiency of the \u201cgreedy\u201d algorithm . In Proceedings of the 7th South Eastern Conference on Combinatorics, Graph Theory and Computing. 341--350 . T. A. Jenkyns. 1976. The efficiency of the \u201cgreedy\u201d algorithm. In Proceedings of the 7th South Eastern Conference on Combinatorics, Graph Theory and Computing. 341--350."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9596-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0592"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/090750020"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1100.0463"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_31_1","volume-title":"Vazirani","author":"Nisan Noam","year":"2007","unstructured":"Noam Nisan , Tim Roughgarden , Eva Tardos , and Vijay V . Vazirani . 2007 . Algorithmic Game Theory. Cambridge University Press . Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press."},{"volume-title":"Combinatorial Optimization","author":"Schrijver A.","key":"e_1_2_1_32_1","unstructured":"A. Schrijver . 2003. Combinatorial Optimization . Springer . A. Schrijver. 2003. Combinatorial Optimization. Springer."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the Innovations in Computer Science. 195--210","author":"Seshadhri C.","year":"2011","unstructured":"C. Seshadhri and Jan Vondr\u00e1k . 2011 . Is submodularity testable? In Proceedings of the Innovations in Computer Science. 195--210 . C. Seshadhri and Jan Vondr\u00e1k. 2011. Is submodularity testable? In Proceedings of the Innovations in Computer Science. 195--210."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.62"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796314240"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2746226","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2746226","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:16:44Z","timestamp":1750227404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2746226"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,16]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2,8]]}},"alternative-id":["10.1145\/2746226"],"URL":"https:\/\/doi.org\/10.1145\/2746226","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2015,11,16]]},"assertion":[{"value":"2011-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}