{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T02:33:42Z","timestamp":1774406022669,"version":"3.50.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T00:00:00Z","timestamp":1597363200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T00:00:00Z","timestamp":1597363200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1357\/16"],"award-info":[{"award-number":["1357\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,3]]},"DOI":"10.1007\/s00453-020-00757-9","type":"journal-article","created":{"date-parts":[[2020,8,14]],"date-time":"2020-08-14T11:27:00Z","timestamp":1597404420000},"page":"853-878","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["Guess Free Maximization of Submodular and Linear Sums"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1535-2979","authenticated-orcid":false,"given":"Moran","family":"Feldman","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,8,14]]},"reference":[{"key":"757_CR1","doi-asserted-by":"crossref","unstructured":"Adamczyk, M., Wlodarczyk, M.: Random order contention resolution schemes. In: FOCS, pp. 790\u2013801 (2018)","DOI":"10.1109\/FOCS.2018.00080"},{"key":"757_CR2","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154","volume-title":"The Probabilistic Method","author":"N Alon","year":"2000","unstructured":"Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. Wiley, London (2000)","edition":"2"},{"key":"757_CR3","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: SODA, pp. 1497\u20131514 (2014)","DOI":"10.1137\/1.9781611973402.110"},{"issue":"3","key":"757_CR4","doi-asserted-by":"publisher","first-page":"988","DOI":"10.1287\/moor.2018.0955","volume":"44","author":"N Buchbinder","year":"2019","unstructured":"Buchbinder, N., Feldman, M.: Constrained submodular maximization via a non-symmetric technique. Math. Oper. Res. 44(3), 988\u20131005 (2019)","journal-title":"Math. Oper. Res."},{"key":"757_CR5","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: Submodular maximization with cardinality constraints. In: SODA, pp. 1433\u20131452 (2014)","DOI":"10.1137\/1.9781611973402.106"},{"issue":"2","key":"757_CR6","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1287\/moor.2016.0809","volume":"42","author":"N Buchbinder","year":"2017","unstructured":"Buchbinder, N., Feldman, M., Schwartz, R.: Comparing apples and oranges: query trade-off in submodular maximization. Math. Oper. Res. 42(2), 308\u2013329 (2017)","journal-title":"Math. Oper. Res."},{"issue":"6","key":"757_CR7","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G C\u0103linescu","year":"2011","unstructured":"C\u0103linescu, 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":"757_CR8","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: FOCS, pp. 575\u2013584 (2010)","DOI":"10.1109\/FOCS.2010.60"},{"issue":"6","key":"757_CR9","doi-asserted-by":"publisher","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."},{"key":"757_CR10","doi-asserted-by":"crossref","unstructured":"Ene, A., Nguyen, H.L.: Constrained submodular maximization: Beyond 1\/e. In: FOCS, pp. 248\u2013257 (2016)","DOI":"10.1109\/FOCS.2016.34"},{"key":"757_CR11","doi-asserted-by":"crossref","unstructured":"Feldman, M.: Maximizing symmetric submodular functions. ACM Trans. Algorithms 13(3), 39:1\u201339:36 (2017)","DOI":"10.1145\/3070685"},{"key":"757_CR12","doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: FOCS, pp. 570\u2013579 (2011)","DOI":"10.1109\/FOCS.2011.46"},{"key":"757_CR13","doi-asserted-by":"crossref","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes. In: SODA, pp. 1014\u20131033 (2016)","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"757_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, A., Nagarajan, V.: A stochastic probing problem with applications. In: IPCO, pp. 205\u2013216 (2013)","DOI":"10.1007\/978-3-642-36694-9_18"},{"key":"757_CR15","unstructured":"Harshaw, C., Feldman, M., Ward, J., Karbasi, A.: Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In: ICML, pp. 2634\u20132643 (2019)"},{"issue":"3","key":"757_CR16","doi-asserted-by":"publisher","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."},{"key":"757_CR17","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. Math. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"757_CR18","doi-asserted-by":"crossref","unstructured":"Soma, T., Yoshida, Y.: A new approximation guarantee for monotone submodular function maximization via discrete convexity. In: ICALP, pp. 99:1\u201399:14 (2018)","DOI":"10.1609\/aaai.v31i1.10653"},{"issue":"4","key":"757_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. Math. Oper. Res. 42(4), 1197\u20131218 (2017)","journal-title":"Math. Oper. Res."}],"updated-by":[{"DOI":"10.1007\/s00453-022-01028-5","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T00:00:00Z","timestamp":1661904000000}}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00757-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00757-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00757-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T12:09:13Z","timestamp":1661947753000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00757-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,14]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["757"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00757-9","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s00453-022-01028-5","asserted-by":"object"}]},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,14]]},"assertion":[{"value":"20 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2022","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00453-022-01028-5","URL":"https:\/\/doi.org\/10.1007\/s00453-022-01028-5","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}