{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T14:08:49Z","timestamp":1774966129571,"version":"3.50.1"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,8,29]],"date-time":"2018-08-29T00:00:00Z","timestamp":1535500800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,8,29]],"date-time":"2018-08-29T00:00:00Z","timestamp":1535500800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-1422658"],"award-info":[{"award-number":["CCF-1422658"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,5]]},"DOI":"10.1007\/s10878-018-0345-z","type":"journal-article","created":{"date-parts":[[2018,8,30]],"date-time":"2018-08-30T01:07:48Z","timestamp":1535591268000},"page":"1126-1149","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Improved bounds for the greedy strategy in optimization problems with curvature"],"prefix":"10.1007","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5467-5976","authenticated-orcid":false,"given":"Yajing","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edwin K. P.","family":"Chong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ali","family":"Pezeshki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,29]]},"reference":[{"issue":"2","key":"345_CR1","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0166-218X(02)00455-9","volume":"131","author":"E Boros","year":"2003","unstructured":"Boros E, Elbassioni K, Gurvich V, Khachiyan L (2003) An inequality for polymatroid functions and its applications. Discrete Appl Math 131(2):255\u2013281","journal-title":"Discrete Appl Math"},{"key":"345_CR2","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, Cornu\u00e9jols G (1984) Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado\u2013Edmonds theorem. Discrete Appl Math 7:251\u2013274","journal-title":"Discrete Appl Math"},{"key":"345_CR3","first-page":"11","volume":"2570","author":"J Edmonds","year":"2003","unstructured":"Edmonds J (2003) Submodular functions, matroids, and certain polyhedra. Comb Optim 2570:11\u201326","journal-title":"Comb Optim"},{"key":"345_CR4","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"ML Fisher","year":"1978","unstructured":"Fisher ML, Nemhauser GL, Wolsey LA (1978) An analysis of approximations for maximizing submodular set functions\u2014II. Math Program Stud 8:73\u201387","journal-title":"Math Program Stud"},{"issue":"2","key":"345_CR5","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s10957-017-1177-1","volume":"177","author":"Y Liu","year":"2018","unstructured":"Liu Y, Zhang Z, Chong EKP, Pezeshki A (2018) Performance bounds with curvature for batched greedy strategy. J Optim Theory Appl 177(2):535\u2013562","journal-title":"J Optim Theory Appl"},{"key":"345_CR6","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions\u2014I. Math Program Stud 14:265\u2013294","journal-title":"Math Program Stud"},{"key":"345_CR7","unstructured":"Singh AP, Guillory A, Bilmes J (2012) On bisubmodular maximization. In: Proceedings of 15th international conference on artificial intelligence and statistics, pp\u00a01055\u20131063"},{"key":"345_CR8","unstructured":"Streeter M, Golovin D (2008) An online algorithm for maximizing submodular functions. In: Proceedings of advances in neural information processing systems, pp\u00a01577\u20131584"},{"key":"345_CR9","doi-asserted-by":"crossref","unstructured":"Sviridenko M, Vondr\u00e1k J, Ward J (2015) Optimal approximation for submodular and supermodular optimization with bounded curvature. In: Proceedings of 26th annual ACM-SIAM symposium. Discrete algorithms, pp\u00a01134\u20131148","DOI":"10.1137\/1.9781611973730.76"},{"key":"345_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.6028\/jres.069B.001","volume":"69B","author":"WT Tutte","year":"1965","unstructured":"Tutte WT (1965) Lecture on matroids. J Res Natl Bur Stand B Math Math Phys 69B:1\u201347","journal-title":"J Res Natl Bur Stand B Math Math Phys"},{"key":"345_CR11","first-page":"253","volume":"B23","author":"J Vondr\u00e1k","year":"2010","unstructured":"Vondr\u00e1k J (2010) Submodularity and curvature: the optimal algorithm. RIMS Kokyuroku Bessatsu B23:253\u2013266","journal-title":"RIMS Kokyuroku Bessatsu"},{"issue":"3","key":"345_CR12","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1109\/TAC.2015.2440566","volume":"61","author":"Z Zhang","year":"2016","unstructured":"Zhang Z, Chong EKP, Pezeshki A, Moran W (2016) String submodular functions with curvature constraints. IEEE Trans Autom 61(3):601\u2013616","journal-title":"IEEE Trans Autom"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0345-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0345-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0345-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T12:48:39Z","timestamp":1589719719000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0345-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,29]]},"references-count":12,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["345"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0345-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,29]]},"assertion":[{"value":"29 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}