{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:14:30Z","timestamp":1781259270365,"version":"3.54.1"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030218027","type":"print"},{"value":"9783030218034","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,6,15]],"date-time":"2019-06-15T00:00:00Z","timestamp":1560556800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-21803-4_49","type":"book-chapter","created":{"date-parts":[[2019,6,15]],"date-time":"2019-06-15T02:03:24Z","timestamp":1560564204000},"page":"488-497","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Stochastic Greedy Algorithm Is Still Good: Maximizing Submodular + Supermodular Functions"],"prefix":"10.1007","author":[{"given":"Sai","family":"Ji","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Min","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yishui","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dongmei","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,6,15]]},"reference":[{"key":"49_CR1","unstructured":"Bai, W., Bilmes, J.A.: Greed is still good: maximizing monotone submodular+ supermodular functions (2018). arXiv preprint arXiv:1801.07413"},{"key":"49_CR2","unstructured":"Bian, A., Levy, K., Krause, A., Buhmann, J.M.: Continuous dr-submodular maximization: structure and algorithms. In: Advances in Neural Information Processing Systems, pp. 486\u2013496 (2017)"},{"key":"49_CR3","unstructured":"Bian, A.A., Buhmann, J.M., Krause, A., Tschiatschek, S.: Guarantees for greedy maximization of non-submodular functions with applications (2017). arXiv preprint arXiv:1703.02100"},{"key":"49_CR4","unstructured":"Bogunovic, I., Zhao, J., Cevher, V.: Robust maximization of non-submodular objectives (2018). arXiv preprint arXiv:1802.07073"},{"key":"49_CR5","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J.S., Schwartz, R.: Submodular maximization with cardinality constraints. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1433\u20131452 (2014)","DOI":"10.1137\/1.9781611973730.80"},{"issue":"6","key":"49_CR6","doi-asserted-by":"crossref","first-page":"1831","DOI":"10.1137\/110839655","volume":"43","author":"C Chekuri","year":"2014","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6), 1831\u20131879 (2014)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"49_CR7","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","volume":"7","author":"M Conforti","year":"1984","unstructured":"Conforti, M., Cornu\u00e9jols, G.: Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the rado-edmonds theorem. Discret. Appl. Math. 7(3), 251\u2013274 (1984)","journal-title":"Discret. Appl. Math."},{"key":"49_CR8","doi-asserted-by":"crossref","unstructured":"Epasto, A., Lattanzi, S., Vassilvitskii, S., Zadimoghaddam, M.: Submodular optimization over sliding windows. In: Proceedings of the 26th International Conference on World Wide Web, pp. 421\u2013430 (2017)","DOI":"10.1145\/3038912.3052699"},{"key":"49_CR9","doi-asserted-by":"crossref","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions - II. Polyhedral Combinatorics, pp. 73\u201387 (1978)","DOI":"10.1007\/BFb0121195"},{"key":"49_CR10","doi-asserted-by":"crossref","unstructured":"Iwata, S., Orlin, J.B.: A simple combinatorial algorithm for submodular function minimization. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1230\u20131237 (2009)","DOI":"10.1137\/1.9781611973068.133"},{"key":"49_CR11","doi-asserted-by":"crossref","unstructured":"Kawase, Y., Sumita, H., Fukunaga, T.: Submodular maximization with uncertain knapsack capacity. In: Latin American Symposium on Theoretical Informatics, pp. 653\u2013668 (2018)","DOI":"10.1007\/978-3-319-77404-6_48"},{"issue":"9","key":"49_CR12","doi-asserted-by":"crossref","first-page":"1645","DOI":"10.1109\/TPAMI.2008.217","volume":"31","author":"P Kohli","year":"2009","unstructured":"Kohli, P., Kumar, M.P., Torr, P.H.: P $$^3$$ & beyond: move making algorithms for solving higher order functions. IEEE Trans. Pattern Anal. Mach. Intell. 31(9), 1645\u20131656 (2009)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"49_CR13","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 (2006)","DOI":"10.1109\/IPSN.2006.244031"},{"key":"49_CR14","unstructured":"Lin, H., Bilmes, J.: A class of submodular functions for document summarization, pp. 510\u2013520 (2011)"},{"key":"49_CR15","doi-asserted-by":"crossref","unstructured":"Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A., Vondr\u00e1k, J., Krause, A.: Lazier than lazy greedy. In: AAAI, pp. 1812\u20131818 (2015)","DOI":"10.1609\/aaai.v29i1.9486"},{"key":"49_CR16","unstructured":"Narasimhan, M., Bilmes, J.: Pac-learning bounded tree-width graphical models. In: Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, pp. 410\u2013417 (2004)"},{"issue":"1","key":"49_CR17","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. Prog. 14(1), 265\u2013294 (1978)","journal-title":"Math. Prog."},{"key":"49_CR18","unstructured":"Niazadeh, R., Roughgarden, T., Wang, J.R.: Optimal algorithms for continuous non-monotone submodular and dr-submodular maximization (2018). arXiv preprint arXiv:1805.09480"},{"key":"49_CR19","doi-asserted-by":"crossref","unstructured":"Qian, C., Yu, Y., Tang, K.: Approximation guarantees of stochastic greedy algorithms for subset selection. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence IJCAI, pp. 1478\u20131484 (2018)","DOI":"10.24963\/ijcai.2018\/205"},{"key":"49_CR20","doi-asserted-by":"crossref","unstructured":"Schoenebeck, G., Tao, B.: Beyond worst-case (in) approximability of nonsubmodular influence maximization. In: International Conference on Web and Internet Economics, pp. 368\u2013382 (2017)","DOI":"10.1007\/978-3-319-71924-5_26"},{"issue":"1","key":"49_CR21","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":"49_CR22","unstructured":"Wei, K., Iyer, R., Bilmes, J.: Submodularity in data subset selection and active learning. In: International Conference on Machine Learning, pp. 1954\u20131963 (2015)"}],"container-title":["Advances in Intelligent Systems and Computing","Optimization of Complex Systems: Theory, Models, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-21803-4_49","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,20]],"date-time":"2022-09-20T21:22:23Z","timestamp":1663708943000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-21803-4_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,15]]},"ISBN":["9783030218027","9783030218034"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-21803-4_49","relation":{},"ISSN":["2194-5357","2194-5365"],"issn-type":[{"value":"2194-5357","type":"print"},{"value":"2194-5365","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,15]]},"assertion":[{"value":"15 June 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WCGO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"World Congress on Global Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Metz","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wcgo2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}