{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:21:13Z","timestamp":1770895273588,"version":"3.50.1"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031491924","type":"print"},{"value":"9783031491931","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,9]],"date-time":"2023-12-09T00:00:00Z","timestamp":1702080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-49193-1_10","type":"book-chapter","created":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T09:02:36Z","timestamp":1702026156000},"page":"118-143","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The Regularized Submodular Maximization via\u00a0the\u00a0Lyapunov Method"],"prefix":"10.1007","author":[{"given":"Xin","family":"Sun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Congying","family":"Han","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,9]]},"reference":[{"issue":"1","key":"10_CR1","first-page":"1","volume":"15","author":"N Bansal","year":"2019","unstructured":"Bansal, N., Gupta, A.: Potential-function proofs for gradient methods. Theory of Computing 15(1), 1\u201332 (2019)","journal-title":"Theory of Computing"},{"key":"10_CR2","unstructured":"Bian Y, Buhmann JM, Krause A. Continuous submodular function maximization. Preprint arXiv:2006.13474. (2020)"},{"key":"10_CR3","unstructured":"Bodek K, Feldman M. Maximizing sums of non-monotone submodular and linear functions: Understanding the unconstrained case. Preprint arXiv:2204.03412. (2022)"},{"issue":"3","key":"10_CR4","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","volume":"7","author":"M Conforti","year":"1984","unstructured":"Conforti, M., Cornuejols, G.: Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Applied Mathematics 7(3), 251\u2013274 (1984)","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"10_CR5","doi-asserted-by":"publisher","first-page":"660","DOI":"10.1137\/18M1172314","volume":"29","author":"J Diakonikolas","year":"2019","unstructured":"Diakonikolas, J., Orecchia, L.: The approximate duality gap technique: A unified theory of first-order methods. SIAM J. Optim. 29(1), 660\u2013689 (2019)","journal-title":"SIAM J. Optim."},{"key":"10_CR6","unstructured":"Du D, Liu Z, Wu C, Xu D, Zhou Y. An improved approximation algorithm for maximizing a DR-submodular function over a convex set. Preprint arXiv:2203.14740 (2022)"},{"key":"10_CR7","unstructured":"Du D. Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization. Preprint arXiv:2205.12442 (2022)"},{"key":"10_CR8","unstructured":"Du D. Submodularity and lattice: theory, algorithms and applications. Unpublished book (in preparation) (2022)"},{"issue":"3","key":"10_CR9","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s00453-020-00757-9","volume":"83","author":"M Feldman","year":"2021","unstructured":"Feldman, M.: Guess free maximization of submodular and linear sums. Algorithmica 83(3), 853\u2013878 (2021)","journal-title":"Algorithmica"},{"issue":"10","key":"10_CR10","doi-asserted-by":"publisher","first-page":"3101","DOI":"10.1007\/s00453-022-01028-5","volume":"84","author":"M Feldman","year":"2022","unstructured":"Feldman, M.: Correction to: Guess free maximization of submodular and linear sums. Algorithmica 84(10), 3101\u20133102 (2022)","journal-title":"Algorithmica"},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"Feldman M, Naor J, Schwartz R. A unified continuous greedy algorithm for submodular maximization. In Proceedings of the 52nd Annual Symposium on Foundations of Computer Science, pp. 570\u2013579 (2011)","DOI":"10.1109\/FOCS.2011.46"},{"key":"10_CR12","doi-asserted-by":"publisher","first-page":"292","DOI":"10.2307\/1967124","volume":"20","author":"TH Gr\u00f6nwall","year":"1919","unstructured":"Gr\u00f6nwall, T.H.: Note on the derivatives with respect to a parameter of the solutions of a system of differential equations. Ann. Math. 20, 292\u2013296 (1919). https:\/\/doi.org\/10.2307\/1967124","journal-title":"Ann. Math."},{"key":"10_CR13","unstructured":"Hassani H, Soltanolkotabi M, Karbasi A. Gradient methods for submodular maximization. In Proceedings of the 30th International Conference on Advances in Neural Information Processing Systems, pp. 5841\u20135851 (2017)"},{"key":"10_CR14","unstructured":"Krichene K, Bayen A, Bartlett PL. Accelerated mirror descent in continuous and discrete time. In Proceedings of the 28th International Conference on Advances in Neural Information Processing Systems, pp. 2845\u20132853 (2015)"},{"issue":"3","key":"10_CR15","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1080\/00207179208934253","volume":"55","author":"AM Lyapunov","year":"1992","unstructured":"Lyapunov, A.M.: The general problem of the stability of motion. Int. J. Control 55(3), 531\u2013534 (1992)","journal-title":"Int. J. Control"},{"key":"10_CR16","unstructured":"Lu C, Yang W, Gao S. Regularized non-monotone submodular maximization. Preprint arXiv:2103.10008"},{"key":"10_CR17","volume-title":"Problem complexity and method efficiency in optimization","author":"A Nemirovsky","year":"1983","unstructured":"Nemirovsky, A., Yudin, D.B.: Problem complexity and method efficiency in optimization. John Wiley, New York (1983)"},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"Qi B. On maximizing sums of non-monotone submodular and linear functions. Preprint arXiv:2205.15874 (2022)","DOI":"10.1007\/s00453-023-01183-3"},{"issue":"4","key":"10_CR19","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1287\/moor.2016.0842","volume":"42","author":"M Sviridenko","year":"2017","unstructured":"Sviridenko, M., Vondr\u00e1k, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. Mathematics of Operations Research 42(4), 1197\u20131218 (2017)","journal-title":"Mathematics of Operations Research"},{"key":"10_CR20","first-page":"1","volume":"17","author":"W Su","year":"2016","unstructured":"Su, W., Boyd, S., Candes, E.J.: A differential equation for modeling Nesterov\u2019s accelerated gradient method: Theory and insights. Journal of Machine Learning Research 17, 1\u201343 (2016)","journal-title":"Journal of Machine Learning Research"},{"issue":"47","key":"10_CR21","doi-asserted-by":"publisher","first-page":"E7351","DOI":"10.1073\/pnas.1614734113","volume":"113","author":"A Wibisono","year":"2016","unstructured":"Wibisono, A., Wilson, A.C., Jordan, M.I.: A variational perspective on accelerated methods in optimization. In Proceedings of the National Academy of Sciences 113(47), E7351\u2013E7358 (2016)","journal-title":"In Proceedings of the National Academy of Sciences"},{"key":"10_CR22","first-page":"1","volume":"22","author":"AC Wilson","year":"2021","unstructured":"Wilson, A.C., Recht, B., Jordan, M.I.: A Lyapunov analysis of momentum methods in optimization. Journal of Machine Learning Research 22, 1\u201334 (2021)","journal-title":"Journal of Machine Learning Research"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-49193-1_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T09:04:41Z","timestamp":1702026281000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-49193-1_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,9]]},"ISBN":["9783031491924","9783031491931"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-49193-1_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,9]]},"assertion":[{"value":"9 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hawaii, HI","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/COCOON2023\/org.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Springer EquinOCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"146","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"60","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}