{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T15:27:13Z","timestamp":1767108433601,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141645"},{"type":"electronic","value":"9783642141652"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14165-2_23","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T13:26:02Z","timestamp":1278336362000},"page":"262-274","source":"Crossref","is-referenced-by-count":8,"title":["Thresholded Covering Algorithms for Robust and Max-min Optimization"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, S., Ding, Y., Saberi, A., Ye, Y.: Correlation Robust Stochastic Optimization. In: SODA (2010)","DOI":"10.1137\/1.9781611973075.88"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, S.: The Online Set Cover Problem. In: STOC, pp. 100\u2013105 (2003)","DOI":"10.1145\/780555.780558"},{"key":"23_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-72792-7_15","volume-title":"Integer Programming and Combinatorial Optimization","author":"G. Calinescu","year":"2007","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function under a matroid constraint. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 182\u2013196. Springer, Heidelberg (2007)"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Dhamdhere, K., Goyal, V., Ravi, R., Singh, M.: How to pay, come what may: Approximation algorithms for demand-robust covering problems. In: FOCS, pp. 367\u2013378 (2005)","DOI":"10.1109\/SFCS.2005.42"},{"issue":"3","key":"23_CR5","doi-asserted-by":"publisher","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. System Sci.\u00a069(3), 485\u2013497 (2004)","journal-title":"J. Comput. System Sci."},{"key":"23_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/978-3-540-72792-7_33","volume-title":"Integer Programming and Combinatorial Optimization","author":"U. Feige","year":"2007","unstructured":"Feige, U., Jain, K., Mahdian, M., Mirrokni, V.S.: Robust combinatorial optimization with exponential scenarios. In: Fischetti, M., Williamson, D.P. (eds.) IPCO 2007. LNCS, vol.\u00a04513, pp. 439\u2013453. Springer, Heidelberg (2007)"},{"key":"23_CR7","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"M.L. Fisher","year":"1978","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions II. Mathematical Programming Study\u00a08, 73\u201387 (1978)","journal-title":"Mathematical Programming Study"},{"issue":"1","key":"23_CR8","doi-asserted-by":"publisher","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\u00a053(1), 55\u201384 (2004)","journal-title":"J. Algorithms"},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-mst problem in graphs. In: STOC 2005: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pp. 396\u2013402 (2005)","DOI":"10.1145\/1060590.1060650"},{"key":"23_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/11672142_16","volume-title":"STACS 2006","author":"D. Golovin","year":"2006","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: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 206\u2013217. Springer, Heidelberg (2006)"},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"Golovin, D., Nagarajan, V., Singh, M.: Approximating the k-multicut problem. In: SODA 2006: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pp. 621\u2013630 (2006)","DOI":"10.1145\/1109557.1109625"},{"key":"23_CR12","doi-asserted-by":"crossref","unstructured":"Gupta, A., Hajiaghayi, M.T., Nagarajan, V., Ravi, R.: Dial a ride from k-forest. In: Proceedings of the 15th Annual European Symposium on Algorithms, pp. 241\u2013252 (2007)","DOI":"10.1007\/978-3-540-75520-3_23"},{"key":"23_CR13","unstructured":"Gupta, A., Nagarajan, V., Ravi, R.: Thresholded covering algorithms for robust and max-min optimization (2009), (full version) http:\/\/arxiv.org\/abs\/0912.1045"},{"key":"23_CR14","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: SODA, pp. 691\u2013700 (2004)"},{"key":"23_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/978-3-540-87744-8_49","volume-title":"Algorithms - ESA 2008","author":"R. Khandekar","year":"2008","unstructured":"Khandekar, R., Kortsarz, G., Mirrokni, V.S., Salavatipour, M.R.: Two-stage robust network design with exponential scenarios. In: Halperin, D., Mehlhorn, K. (eds.) Esa 2008. LNCS, vol.\u00a05193, pp. 589\u2013600. Springer, Heidelberg (2008)"},{"key":"23_CR16","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":"23_CR17","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G.L. Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions I. Mathematical Programming\u00a014, 265\u2013294 (1978)","journal-title":"Mathematical Programming"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"R\u00e4cke, H.: Optimal hierarchical decompositions for congestion minimization in networks. In: STOC, pp. 255\u2013264 (2008)","DOI":"10.1145\/1374376.1374415"},{"key":"23_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/978-3-540-25960-2_8","volume-title":"Integer Programming and Combinatorial Optimization","author":"R. Ravi","year":"2004","unstructured":"Ravi, R., Sinha, A.: Hedging uncertainty: approximation algorithms for stochastic optimization problems. In: Bienstock, D., Nemhauser, G.L. (eds.) IPCO 2004. LNCS, vol.\u00a03064, pp. 101\u2013115. Springer, Heidelberg (2004)"},{"key":"23_CR20","doi-asserted-by":"crossref","unstructured":"Shmoys, D., Swamy, C.: Stochastic Optimization is (almost) as Easy as Deterministic Optimization. In: FOCS, pp. 228\u2013237 (2004)","DOI":"10.1109\/FOCS.2004.62"},{"issue":"5","key":"23_CR21","doi-asserted-by":"publisher","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.\u00a064(5), 251\u2013254 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"23_CR22","doi-asserted-by":"publisher","first-page":"648","DOI":"10.1137\/S0097539796314240","volume":"29","author":"A. Srinivasan","year":"1999","unstructured":"Srinivasan, A.: Improved approximation guarantees for packing and covering integer programs. SIAM J. Comput.\u00a029(2), 648\u2013670 (1999)","journal-title":"SIAM J. Comput."},{"key":"23_CR23","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 knapsack constraint. Operations Research Letters\u00a032, 41\u201343 (2004)","journal-title":"Operations Research Letters"},{"key":"23_CR24","unstructured":"Swamy, C.: Algorithms for Probabilistically-Constrained Models of Risk-Averse Stochastic Optimization with Black-Box Distributions (2008), http:\/\/arxiv.org\/abs\/0805.0389"},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: STOC, pp. 67\u201374 (2008)","DOI":"10.1145\/1374376.1374389"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14165-2_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T16:31:27Z","timestamp":1740241887000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14165-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141645","9783642141652"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14165-2_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}