{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T20:11:08Z","timestamp":1742933468193,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030581497"},{"type":"electronic","value":"9783030581503"}],"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"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","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-58150-3_42","type":"book-chapter","created":{"date-parts":[[2020,8,27]],"date-time":"2020-08-27T01:02:42Z","timestamp":1598490162000},"page":"520-531","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Parallelized Maximization of Nonsubmodular Function Subject to a Cardinality Constraint"],"prefix":"10.1007","author":[{"given":"Hongxiang","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Longkun","family":"Guo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingjing","family":"Tan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,27]]},"reference":[{"key":"42_CR1","doi-asserted-by":"crossref","unstructured":"Balkanski E, Rubinstein A, Singer Y. An exponential speedup in parallel running time for submodular maximization without loss in approximation. In: Proceedings of SODA, 2019, pp. 283\u2013302","DOI":"10.1137\/1.9781611975482.19"},{"key":"42_CR2","doi-asserted-by":"crossref","unstructured":"Balkanski E, Singer Y. The adaptive complexity of maximizing a submodular function. In: Proceedings of STOC, 2018, pp. 1138\u20131151","DOI":"10.1145\/3188745.3188752"},{"key":"42_CR3","unstructured":"Bian A, Buhmann M, Krause A, Tschiatschek, S. Guarantees for greedy maximization of non-submodular functions with applications. In: Proceedings of ICML, 2017, pp. 498\u2013507"},{"key":"42_CR4","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1016\/j.endm.2010.05.086","volume":"36","author":"M Bouhtou","year":"2010","unstructured":"Bouhtou, M., Stephane, G., Guillaume, S.: Submodularity and randomized rounding techniques for optimal experimental design. Electronic Notes in Discrete Mathematics 36, 679\u2013686 (2010)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"42_CR5","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., Pal, M.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing 40, 1740\u20131766 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"42_CR6","doi-asserted-by":"crossref","unstructured":"Chekuri C, Jayram T S, Vondr$$\\acute{\\rm a}$$k J. On multiplicative weight updates for concave and submodular function maximization. In: Proceedings of CITCS, 2015, pp. 201\u2013210","DOI":"10.1145\/2688073.2688086"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri C, Quanrud K. Submodular function maximization in parallel via the multilinear relaxation. In: Proceedings of SODA, 2019, pp. 303\u2013322","DOI":"10.1137\/1.9781611975482.20"},{"key":"42_CR8","doi-asserted-by":"crossref","unstructured":"Chekuri C, Vondr$$\\acute{\\rm a}$$k J, Zenklusen R. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Computing, 2014, 43: 1831\u20131879","DOI":"10.1137\/110839655"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Conforti M, Cornu$$\\acute{\\rm e}$$jols G. Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Applied Mathematics, 1984, 7: 251\u2013274","DOI":"10.1016\/0166-218X(84)90003-9"},{"key":"42_CR10","unstructured":"Das A, Kempe D. Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Proceedings of ICML, 2011, pp. 1057\u20131064"},{"key":"42_CR11","doi-asserted-by":"crossref","unstructured":"Ene A, Nguy$$\\tilde{\\hat{\\rm e}}$$n H L. Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In: Proceedings of SODA, 2019, pp. 274\u2013282","DOI":"10.1137\/1.9781611975482.18"},{"key":"42_CR12","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF01651330","volume":"22","author":"CM Fortuin","year":"1971","unstructured":"Fortuin, C.M., Kasteleyn, P.W., Ginibre, J.: Correlation inequalities on some partially ordered sets. Communications in Mathematical Physics 22, 89\u2013103 (1971)","journal-title":"Communications in Mathematical Physics"},{"issue":"3","key":"42_CR13","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1007\/s10898-019-00800-2","volume":"75","author":"Suning Gong","year":"2019","unstructured":"Gong, Suning, Nong, Qingqin, Liu, Wenjing, Fang, Qizhi: Parametric monotone function maximization with matroid constraints. Journal of Global Optimization 75(3), 833\u2013849 (2019). https:\/\/doi.org\/10.1007\/s10898-019-00800-2","journal-title":"Journal of Global Optimization"},{"key":"42_CR14","unstructured":"Jegelka S, Bilmes J. Submodularity beyond submodular energies: coupling edges in graph cuts. In: Proceedings of CVPR, 2011, pp. 1897\u20131904"},{"key":"42_CR15","doi-asserted-by":"crossref","unstructured":"Liu Y, Wei K, Kirchhoff K. Submodular feature selection for high-dimensional acoustic score spaces. In: Proceedings of ICA, 2013, pp. 7184\u20137188","DOI":"10.1109\/ICASSP.2013.6639057"},{"key":"42_CR16","doi-asserted-by":"publisher","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. Mathematical Programming 14, 265\u2013294 (1978)","journal-title":"Mathematical Programming"},{"key":"42_CR17","doi-asserted-by":"crossref","unstructured":"Parotsidis N, Pitoura E, Tsaparas P. Centrality-aware link recommendations. In: Proceedings of WSDM, 2016, pp. 503\u2013512","DOI":"10.1145\/2835776.2835818"},{"key":"42_CR18","doi-asserted-by":"crossref","unstructured":"Vondr$$\\acute{\\rm a}$$k J. Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of STOC, 2008, pp. 67\u201374","DOI":"10.1145\/1374376.1374389"},{"key":"42_CR19","unstructured":"Vondr$$\\acute{\\rm a}$$k J. Submodularity and curvature: The optimal algorithm. Annals of Discrete Math, 1978, 2: 65\u201374"}],"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-030-58150-3_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,24]],"date-time":"2021-04-24T05:41:34Z","timestamp":1619242894000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-58150-3_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030581497","9783030581503"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-58150-3_42","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":"27 August 2020","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":"Atlanta, GA","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":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 August 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 August 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon-conference.org\/2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"126","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":"54","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":"43% - 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":"2.7","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":"10.2","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)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}