{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T04:42:16Z","timestamp":1725856936236},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319334608"},{"type":"electronic","value":"9783319334615"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-33461-5_26","type":"book-chapter","created":{"date-parts":[[2016,5,24]],"date-time":"2016-05-24T18:35:59Z","timestamp":1464114959000},"page":"312-324","source":"Crossref","is-referenced-by-count":18,"title":["Robust Monotone Submodular Function Maximization"],"prefix":"10.1007","author":[{"given":"James B.","family":"Orlin","sequence":"first","affiliation":[]},{"given":"Andreas S.","family":"Schulz","sequence":"additional","affiliation":[]},{"given":"Rajan","family":"Udwani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,25]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: SODA 2014, pp. 1497\u20131514. SIAM (2014)","DOI":"10.1137\/1.9781611973402.110"},{"key":"26_CR2","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":"26_CR3","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1137\/080734510","volume":"53","author":"D Bertsimas","year":"2011","unstructured":"Bertsimas, D., Brown, D., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53(3), 464\u2013501 (2011)","journal-title":"SIAM Rev."},{"issue":"1\u20133","key":"26_CR4","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s10107-003-0396-4","volume":"98","author":"D Bertsimas","year":"2003","unstructured":"Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program. 98(1\u20133), 49\u201371 (2003)","journal-title":"Math. Program."},{"issue":"1","key":"26_CR5","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1287\/opre.1030.0065","volume":"52","author":"D Bertsimas","year":"2004","unstructured":"Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52(1), 35\u201353 (2004)","journal-title":"Oper. Res."},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. CoRR, abs\/1508.02157 (2015)","DOI":"10.1137\/1.9781611974331.ch29"},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J.S., Schwartz, R.: A tight linear time (1\/2)-approximation for unconstrained submodular maximization. In: FOCS 2012, pp. 649\u2013658 (2012)","DOI":"10.1109\/FOCS.2012.73"},{"issue":"6","key":"26_CR8","doi-asserted-by":"crossref","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, 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."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Dobzinski, S., Vondr\u00e1k, J.: From query complexity to computational complexity. In: STOC 2012, pp. 1107\u20131116. ACM (2012)","DOI":"10.1145\/2213977.2214076"},{"issue":"4","key":"26_CR10","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 (JACM) 45(4), 634\u2013652 (1998)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"26_CR11","doi-asserted-by":"crossref","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondrak, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J.S., Schwartz, R.: A unified continuous greedy algorithmfor submodular maximization. In: FOCS 2011, pp. 570\u2013579. IEEE","DOI":"10.1109\/FOCS.2011.46"},{"key":"26_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/978-3-642-22006-7_29","volume-title":"Automata, Languages and Programming","author":"M Feldman","year":"2011","unstructured":"Feldman, M., Naor, J.S., Schwartz, R.: Nonmonotone submodular maximization via a structural continuous greedy algorithm. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 342\u2013353. Springer, Heidelberg (2011)"},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Vondr\u00e1k, J.: Submodular maximization by simulatedannealing. In: SODA 2011, pp. 1098\u20131116. SIAM","DOI":"10.1137\/1.9781611973082.83"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Globerson, A., Roweis, S.: Nightmare at test time: robust learning by feature deletion. In Proceedings of the 23rd International Conference on Machine Learning, pp. 353\u2013360. ACM (2006)","DOI":"10.1145\/1143844.1143889"},{"key":"26_CR16","first-page":"427","volume":"42","author":"D Golovin","year":"2011","unstructured":"Golovin, D., Krause, A.: Adaptive submodularity: theory and applications in active learning and stochastic optimization. J. Artif. Intell. Res. 42, 427\u2013486 (2011)","journal-title":"J. Artif. Intell. Res."},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Guestrin, C., Krause, A., Singh, A.P.: Near-optimal sensor placements in Gaussian processes. In: Proceedings of the 22nd International Conference on Machine Learning, pp. 265\u2013272. ACM (2005)","DOI":"10.1145\/1102351.1102385"},{"issue":"4","key":"26_CR18","doi-asserted-by":"crossref","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 (JACM) 48(4), 761\u2013777 (2001)","journal-title":"J. ACM (JACM)"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Krause, A., Guestrin, C., Gupta, A., Kleinberg, J.: Near-optimal sensor placements: Maximizing information while minimizing communication cost. In: Proceedings of the 5th International Conference on Information Processing in Sensor Networks, pp. 2\u201310. ACM (2006)","DOI":"10.1145\/1127777.1127782"},{"key":"26_CR20","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":"26_CR21","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Krause, A. Guestrin, C., Faloutsos, C., VanBriesen, J., Glance, N.: Cost-effective outbreak detection in networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 420\u2013429. ACM (2007)","DOI":"10.1145\/1281192.1281239"},{"key":"26_CR22","doi-asserted-by":"crossref","unstructured":"Liu, Y., Wei, K., Kirchhoff, K., Song, Y., Bilmes, J.: Submodular feature selection for high-dimensional acoustic score spaces. In: 2013 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 7184\u20137188. IEEE (2013)","DOI":"10.1109\/ICASSP.2013.6639057"},{"issue":"3","key":"26_CR23","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177\u2013188 (1978)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"26_CR24","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\u2013I. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"issue":"2","key":"26_CR25","doi-asserted-by":"crossref","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. Theor. Ser. B 80(2), 346\u2013355 (2000)","journal-title":"J. Comb. Theor. Ser. B"},{"issue":"1","key":"26_CR26","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 a knapsack constraint. Oper. Res. Lett. 32(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"key":"26_CR27","doi-asserted-by":"crossref","unstructured":"Thoma, M., Cheng, H., Gretton, A., Han, J., Kriegel, H.P., Smola, A.J., Song, L., Philip, S.Y., Yan, X., Borgwardt, K.M.: Near-optimal supervised feature selection among frequent subgraphs. In: SDM, pp. 1076\u20131087. SIAM (2009)","DOI":"10.1137\/1.9781611972795.92"},{"key":"26_CR28","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: STOC 2008, pp. 67\u201374. ACM","DOI":"10.1145\/1374376.1374389"},{"issue":"1","key":"26_CR29","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1137\/110832318","volume":"42","author":"J Vondr\u00e1k","year":"2013","unstructured":"Vondr\u00e1k, J.: Symmetry and approximability of submodular maximization problems. SIAM J. Comput. 42(1), 265\u2013304 (2013)","journal-title":"SIAM J. Comput."},{"key":"26_CR30","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J., Chekuri, C., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: STOC 2011, pp. 783\u2013792. ACM (2011)","DOI":"10.1145\/1993636.1993740"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-33461-5_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,8]],"date-time":"2019-09-08T15:46:58Z","timestamp":1567957618000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-33461-5_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319334608","9783319334615"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-33461-5_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}