{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T00:59:55Z","timestamp":1740099595501,"version":"3.37.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030416713"},{"type":"electronic","value":"9783030416720"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"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-41672-0_10","type":"book-chapter","created":{"date-parts":[[2020,2,20]],"date-time":"2020-02-20T07:03:04Z","timestamp":1582182184000},"page":"172-186","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0895-7793","authenticated-orcid":false,"given":"Qingqin","family":"Nong","sequence":"first","affiliation":[]},{"given":"Suning","family":"Gong","sequence":"additional","affiliation":[]},{"given":"Qizhi","family":"Fang","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7345-2185","authenticated-orcid":false,"given":"Dingzhu","family":"Du","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,21]]},"reference":[{"issue":"1\u20132","key":"10_CR1","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s10107-009-0298-1","volume":"128","author":"S Ahmed","year":"2011","unstructured":"Ahmed, S., Atamt\u00fcrk, A.: Maximizing a class of submodular utility functions. Math. Program. 128(1\u20132), 149\u2013169 (2011)","journal-title":"Math. Program."},{"issue":"1\u20132","key":"10_CR2","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s10107-018-1248-6","volume":"175","author":"F Bach","year":"2019","unstructured":"Bach, F.: Submodular functions: from discrete to continuous domains. Math. Program. 175(1\u20132), 419\u2013459 (2019)","journal-title":"Math. Program."},{"key":"10_CR3","doi-asserted-by":"crossref","unstructured":"Balcan, M.-F., Harvey, N.-J.-A.: Learning submodular functions. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, pp. 793\u2013802. ACM. San Jose, CA, USA (2011)","DOI":"10.1145\/1993636.1993741"},{"key":"10_CR4","unstructured":"Bian, A., Mirzasoleiman, B., Buhmann, J., Krause, A.: Guaranteed nonconvex optimization: submodular maximization over continuous domains. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 111\u2013120. JMLR. Fort Lauderdale, Florida, USA (2017)"},{"issue":"3","key":"10_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3184990","volume":"14","author":"N Buchbinder","year":"2018","unstructured":"Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms 14(3), 1\u201320 (2018). Article 32","journal-title":"ACM Trans. Algorithms"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J.-S., Schwartz, R.: Submodular maximization with cardinality constraints. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, Oregon, Portland, pp. 1433\u20131452 (2014)","DOI":"10.1137\/1.9781611973402.106"},{"issue":"5","key":"10_CR7","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/130929205","volume":"44","author":"N Buchbinder","year":"2015","unstructured":"Buchbinder, N., Feldman, M., Seffi, J., Schwartz, R.: A tight linear time (1\/2)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5), 1384\u20131402 (2015)","journal-title":"SIAM J. Comput."},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Chen, L., Feldman, M., Karbasi, A.: Unconstrained submodular maximization with constant adaptive complexity. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC, Phoenix, AZ, USA, pp. 102\u2013113 (2019)","DOI":"10.1145\/3313276.3316327"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Ene, A., Nguy$$\\tilde{\\hat{\\text{e}}}$$n, H.-L.: Constrained submodular maximization: beyond $$1\/e$$. In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, New Brunswick, NJ, USA, pp. 248\u2013258 (2016)","DOI":"10.1109\/FOCS.2016.34"},{"key":"10_CR10","unstructured":"Ene, A., Nguy$$\\tilde{\\hat{\\text{ e }}}$$n, H.-L., Vladu, A.: A parallel double greedy algorithm for submodular maximization (2018). https:\/\/arxiv.org\/abs\/1812.01591"},{"issue":"4","key":"10_CR11","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.-S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS, pp. 570\u2013579. Palm Springs, CA, USA (2011)","DOI":"10.1109\/FOCS.2011.46"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Gharan, S.-O., Vondr\u00e1k J.: Submodular maximization by simulated annealing. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1098\u20131117. Society for Industrial and Applied Mathematics, San Francisco, California, USA (2011)","DOI":"10.1137\/1.9781611973082.83"},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-319-28684-6_12","volume-title":"Approximation and Online Algorithms","author":"C Gottschalk","year":"2015","unstructured":"Gottschalk, C., Peis, B.: Submodular function maximization on the bounded integer lattice. In: Sanit\u00e0, L., Skutella, M. (eds.) WAOA 2015. LNCS, vol. 9499, pp. 133\u2013144. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-28684-6_12"},{"key":"10_CR15","doi-asserted-by":"crossref","unstructured":"Hartline, J., Mirrokni, V., Sundararajan, M.: Optimal marketing strategies over social networks. In: Proceedings of the 17th International Conference on World Wide Web, pp. 189\u2013198. ACM. Beijing, China (2008)","DOI":"10.1145\/1367497.1367524"},{"issue":"4","key":"10_CR16","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1145\/502090.502093","volume":"48","author":"DS Hochbaum","year":"2001","unstructured":"Hochbaum, D.S.: An efficient algorithm for image segmentation. Markov random fields and related problems. J. ACM 48(4), 686\u2013701 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"10_CR17","first-page":"269","volume":"69","author":"DS Hochbaum","year":"1995","unstructured":"Hochbaum, D.S., Hong, S.P.: About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Math. Program. 69(1), 269\u2013309 (1995)","journal-title":"Math. Program."},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Post, I., Vondr\u00e1k, J.: Online submodular welfare maximization: greedy is optimal. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1216\u20131225. SIAM, New Orleans, Louisiana, USA (2013)","DOI":"10.1137\/1.9781611973105.88"},{"key":"10_CR19","unstructured":"Niazadeh, R., Roughgarden, T.: Optimal algorithms for continuous non-monotone submodular and DR-submodular maximization. In: the 32nd Conference on Neural Information Processing Systems, NIPS, Montr\u00e9al, Canada, pp. 9617\u20139627 (2018)"},{"key":"10_CR20","unstructured":"Soma, T., Yoshida, Y.: A generalization of submodular cover via the diminishing return property on the integer lattice. In: Advances in Neural Information Processing Systems, pp. 847\u2013855 (2015)"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Soma, T., Yoshida, Y.: Non-monotone DR-submodular function maximization. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp. 898\u2013904. AAAI, San Francisco, California, USA (2017)","DOI":"10.1609\/aaai.v31i1.10653"}],"container-title":["Lecture Notes in Computer Science","Complexity and Approximation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-41672-0_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,16]],"date-time":"2022-10-16T02:28:28Z","timestamp":1665887308000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-41672-0_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030416713","9783030416720"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-41672-0_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"21 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}