{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:34:26Z","timestamp":1759847666647},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2013,8,21]],"date-time":"2013-08-21T00:00:00Z","timestamp":1377043200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2014,8]]},"DOI":"10.1007\/s10107-013-0705-5","type":"journal-article","created":{"date-parts":[[2013,8,20]],"date-time":"2013-08-20T01:02:13Z","timestamp":1376960533000},"page":"583-615","source":"Crossref","is-referenced-by-count":11,"title":["Thresholded covering algorithms for robust and max\u2013min optimization"],"prefix":"10.1007","volume":"146","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,8,21]]},"reference":[{"key":"705_CR1","doi-asserted-by":"crossref","DOI":"10.1515\/9781400831050","volume-title":"Robust Optimization","author":"A Ben-Tal","year":"2009","unstructured":"Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)"},{"issue":"3","key":"705_CR2","doi-asserted-by":"crossref","first-page":"445","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A Agrawal","year":"1995","unstructured":"Agrawal, A., Klein, P., Ravi, R.: When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. 24(3), 445\u2013456 (1995)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"705_CR3","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1287\/opre.1110.1011","volume":"60","author":"S Agrawal","year":"2012","unstructured":"Agrawal, S., Ding, Y., Saberi, A., Ye, Y.: Price of correlations in stochastic optimization. Oper. Res. 60(1), 150\u2013162 (2012)","journal-title":"Oper. Res."},{"issue":"4","key":"705_CR4","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1145\/1198513.1198522","volume":"2","author":"N Alon","year":"2006","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: A general approach to online network optimization problems. ACM Trans. Algorithms 2(4), 640\u2013660 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"2","key":"705_CR5","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1137\/060661946","volume":"39","author":"N Alon","year":"2009","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. SIAM J. Comput. 39(2), 361\u2013370 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"705_CR6","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1287\/moor.23.4.769","volume":"23","author":"A Ben-Tal","year":"1998","unstructured":"Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23(4), 769\u2013805 (1998)","journal-title":"Math. Oper. Res."},{"key":"705_CR7","doi-asserted-by":"crossref","unstructured":"Berman, P., Coulston, C.: On-line algorithms for Steiner tree problems. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 344\u2013353 (1997)","DOI":"10.1145\/258533.258618"},{"issue":"3","key":"705_CR8","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1137\/080734510","volume":"53","author":"D Bertsimas","year":"2011","unstructured":"Bertsimas, D., Brown, D.B., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53(3), 464\u2013501 (2011)","journal-title":"SIAM Rev."},{"issue":"1\u20132","key":"705_CR9","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s10107-005-0677-1","volume":"107","author":"D Bertsimas","year":"2006","unstructured":"Bertsimas, D., Sim, M.: Tractable approximations to robust conic optimization problems. Math. Program. 107(1\u20132), 5\u201336 (2006)","journal-title":"Math. Program."},{"key":"705_CR10","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Laura, S.: An improved LP-based approximation for Steiner tree. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 583\u2013592 (2010)","DOI":"10.1145\/1806689.1806769"},{"issue":"6","key":"705_CR11","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G C\u0103linescu","year":"2011","unstructured":"C\u0103linescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"705_CR12","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1002\/rsa.10033","volume":"20","author":"B Carr","year":"2002","unstructured":"Carr, B., Vempala, S.: Randomized meta-rounding. Random Struct. Algorithms 20(3), 343\u2013352 (2002)","journal-title":"Random Struct. Algorithms"},{"key":"705_CR13","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: The all-or-nothing multicommodity flow problem. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 156\u2013165 (2004)","DOI":"10.1145\/1007352.1007383"},{"key":"705_CR14","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: Multicommodity flow, well-linked terminals, and routing problems. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 183\u2013192 (2005)","DOI":"10.1145\/1060590.1060618"},{"key":"705_CR15","unstructured":"Dhamdhere, K., Goyal, V., Ravi. R., Singh, M.: How to pay, come what may: approximation algorithms for demand-robust covering problems. In: Proceedings of the Symposium on Foundations of Computer Science (FOCS), pp. 367\u2013378 (2005)"},{"issue":"3","key":"705_CR16","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"705_CR17","doi-asserted-by":"crossref","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":"705_CR18","doi-asserted-by":"crossref","unstructured":"Feige, U., Jain, K., Mahdian, M., Mirrokni, V.S.: Robust combinatorial optimization with exponential scenarios. In: Proceedings of the Integer Programming and Combinatorial Optimization Conference (IPCO), pp. 439\u2013453 (2007)","DOI":"10.1007\/978-3-540-72792-7_33"},{"key":"705_CR19","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"ML Fisher","year":"1978","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions II. Math. Program. Study 8, 73\u201387 (1978)","journal-title":"Math. Program. Study"},{"issue":"1","key":"705_CR20","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"R Gandhi","year":"2004","unstructured":"Gandhi, R., Khuller, S., Srinivasan, A.: Approximation algorithms for partial covering problems. J. Algorithms 53(1), 55\u201384 (2004)","journal-title":"J. Algorithms"},{"key":"705_CR21","doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 396\u2013402 (2005)","DOI":"10.1145\/1060590.1060650"},{"issue":"2","key":"705_CR22","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N Garg","year":"1996","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput. 25(2), 235\u2013251 (1996)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"705_CR23","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"705_CR24","doi-asserted-by":"crossref","unstructured":"Golovin, D., Goyal, V., Ravi, R.: Pay today for a rainy day: improved approximation algorithms for demand-robust min-cut and shortest path problems. In: Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS), pp. 206\u2013217 (2006)","DOI":"10.1007\/11672142_16"},{"key":"705_CR25","doi-asserted-by":"crossref","unstructured":"Golovin, D., Nagarajan, V., Singh, M.: Approximating the k-multicut problem. In: Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 621\u2013630 (2006)","DOI":"10.1145\/1109557.1109625"},{"key":"705_CR26","unstructured":"Gupta, A., Hajiaghayi, Mohammad T., Nagarajan, V., Ravi, R.: Dial a Ride from k-forest. ACM Trans. Algorithms 6(2), 1\u201321 (2010)"},{"key":"705_CR27","unstructured":"Gupta, A., Nagarajan, V., Ravi, R.: Robust and max\u2013min optimization under matroid and knapsack uncertainty sets. http:\/\/arxiv.org\/abs\/1012.4962"},{"issue":"5","key":"705_CR28","doi-asserted-by":"crossref","first-page":"1361","DOI":"10.1137\/080732250","volume":"40","author":"A Gupta","year":"2011","unstructured":"Gupta, A., P\u00e1l, M., Ravi, R., Amitabh, S.: Sampling and cost-sharing: approximation algorithms for stochastic optimization problems. SIAM J. Comput. 40(5), 1361\u20131401 (2011)","journal-title":"SIAM J. Comput."},{"key":"705_CR29","doi-asserted-by":"crossref","unstructured":"Harrelson, C., Hildrum, K., Rao, S.: A polynomial-time tree decomposition to minimize congestion. In: Proceedings of the Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 34\u201343 (2003)","DOI":"10.1145\/777412.777419"},{"issue":"3","key":"705_CR30","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M Imase","year":"1991","unstructured":"Imase, M., Waxman, B.M.: Dynamic Steiner tree problem. SIAM J. Discret. Math. 4(3), 369\u2013384 (1991)","journal-title":"SIAM J. Discret. Math."},{"key":"705_CR31","unstructured":"Immorlica, N., Karger, D., Minkoff, M., Mirrokni, V.S.: On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. In: Proceedings of the Symposium on Discrete Algorithms (SODA), pp. 691\u2013700 (2004)"},{"issue":"2","key":"705_CR32","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/s00453-011-9596-0","volume":"65","author":"R Khandekar","year":"2013","unstructured":"Khandekar, R., Kortsarz, G., Mirrokni, V.S., Salavatipour, M.R.: Two-stage robust network design with exponential scenarios. Algorithmica 65(2), 391\u2013408 (2013)","journal-title":"Algorithmica"},{"key":"705_CR33","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"705_CR34","doi-asserted-by":"crossref","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 I. Math. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"705_CR35","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: Proceedings of the Symposium on Theory of Computing (STOC), pp. 255\u2013264 (2008)","DOI":"10.1145\/1374376.1374415"},{"issue":"2","key":"705_CR36","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P Raghavan","year":"1988","unstructured":"Raghavan, P.: Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci. 37(2), 130\u2013143 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"705_CR37","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/s10107-005-0673-5","volume":"108","author":"R Ravi","year":"2006","unstructured":"Ravi, R., Sinha, A.: Approximation algorithms for stochastic optimization problems. Math. Program. 108(1), 97\u2013114 (2006)","journal-title":"Math. Program."},{"key":"705_CR38","volume-title":"Combinatorial Optimization","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization. Springer, Berlin (2003)"},{"issue":"6","key":"705_CR39","doi-asserted-by":"crossref","first-page":"978","DOI":"10.1145\/1217856.1217860","volume":"53","author":"DB Shmoys","year":"2006","unstructured":"Shmoys, D.B., Swamy, C.: An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM 53(6), 978\u20131012 (2006)","journal-title":"J. ACM"},{"issue":"5","key":"705_CR40","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0020-0190(97)00182-8","volume":"64","author":"P Slav\u00edk","year":"1997","unstructured":"Slav\u00edk, P.: Improved performance of the greedy algorithm for partial cover. Inf. Process. Lett. 64(5), 251\u2013254 (1997)","journal-title":"Inf. Process. Lett."},{"key":"705_CR41","doi-asserted-by":"crossref","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 knapsack constraint. Oper. Res. Lett. 32, 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"key":"705_CR42","doi-asserted-by":"crossref","unstructured":"Swamy, C.: Risk-averse stochastic optimization: probabilistically-constrained models and algorithms for black-box distributions. In: SODA, pp. 1627\u20131646 (2011)","DOI":"10.1137\/1.9781611973082.126"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-013-0705-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-013-0705-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-013-0705-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,21]],"date-time":"2019-07-21T07:45:50Z","timestamp":1563695150000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-013-0705-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8,21]]},"references-count":42,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["705"],"URL":"https:\/\/doi.org\/10.1007\/s10107-013-0705-5","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8,21]]}}}