{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:46:10Z","timestamp":1740123970291,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,3,20]],"date-time":"2018-03-20T00:00:00Z","timestamp":1521504000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,3,20]],"date-time":"2018-03-20T00:00:00Z","timestamp":1521504000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1422658"],"award-info":[{"award-number":["CCF-1422658"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s10957-017-1177-1","type":"journal-article","created":{"date-parts":[[2018,3,20]],"date-time":"2018-03-20T16:54:12Z","timestamp":1521564852000},"page":"535-562","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Performance Bounds with Curvature for Batched Greedy Optimization"],"prefix":"10.1007","volume":"177","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":"Zhenliang","family":"Zhang","sequence":"additional","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,3,20]]},"reference":[{"key":"1177_CR1","doi-asserted-by":"crossref","unstructured":"Streeter, M., Golovin, D.: An online algorithm for maximizing submodular functions. In: Proceedings of Advances in Neural Information Processing, pp.\u00a01577\u20131584 (2008)","DOI":"10.21236\/ADA476748"},{"key":"1177_CR2","doi-asserted-by":"crossref","unstructured":"Feige, U., Vondr\u00e1k, J.: Approximation algorithms for allocation problems: improving the factor of $$1-1\/e$$. In: Proceedings of 47th IEEE Symposium on Foundations of Computer Science, pp.\u00a0667\u2013676 (2006)","DOI":"10.1109\/FOCS.2006.14"},{"key":"1177_CR3","doi-asserted-by":"crossref","unstructured":"Fleischer, L., Goemans, M.X., Mirrokni, V.S., Sviridenko, M.: Tight approximation algorithms for maximum general assignment problems. In: Proceedings of 17th Annual ACM-SIAM Symposium Discrete Algorithm, pp.\u00a0611\u2013620 (2006)","DOI":"10.1145\/1109557.1109624"},{"issue":"4","key":"1177_CR4","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.ipl.2006.06.003","volume":"100","author":"R Cohen","year":"2006","unstructured":"Cohen, R., Katzir, L., Raz, D.: An efficient approximation for the generalized assignment problem. Inf. Process. Lett. 100(4), 162\u2013166 (2006)","journal-title":"Inf. Process. Lett."},{"key":"1177_CR5","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/BF01585178","volume":"62","author":"DB Shmoys","year":"1993","unstructured":"Shmoys, D.B., Tardos, \u00c9.: An approximation algorithm for the generalized assignment problem. Math. Program. 62, 461\u2013474 (1993)","journal-title":"Math. Program."},{"issue":"6","key":"1177_CR6","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, 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\u20131746 (2011)","journal-title":"SIAM J. Comput."},{"key":"1177_CR7","doi-asserted-by":"crossref","unstructured":"Korula, N., Mirrokni, V., Zadimoghaddam, M.: Online submodular welfare maximization: Greedy beats 1\/2 in random order. In: Proceedings of 47th Annual Symposium on Theory of Computing, pp.\u00a0889\u2013898 (2015)","DOI":"10.1137\/15M1051142"},{"key":"1177_CR8","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of 40th Annual ACM Symposium on Theory of Computing, pp.\u00a067\u201374 (2008)","DOI":"10.1145\/1374376.1374389"},{"issue":"6","key":"1177_CR9","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1002\/(SICI)1520-6750(199809)45:6<615::AID-NAV5>3.0.CO;2-5","volume":"45","author":"DS Hochbaum","year":"1998","unstructured":"Hochbaum, D.S., Pathria, A.: Analysis of the greedy approach in problems of maximum $$k$$-coverage. Nav. Res. Log. 45(6), 615\u2013627 (1998)","journal-title":"Nav. Res. Log."},{"issue":"4","key":"1177_CR10","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"1177_CR11","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39\u201345 (1999)","journal-title":"Inf. Process. Lett."},{"issue":"8","key":"1177_CR12","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G Cornu\u00e9jols","year":"1977","unstructured":"Cornu\u00e9jols, G., Fisher, M.L., Nemhauser, G.L.: Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manag. Sci. 23(8), 789\u2013810 (1977)","journal-title":"Manag. Sci."},{"issue":"2","key":"1177_CR13","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1137\/0604028","volume":"4","author":"N Megiddo","year":"1983","unstructured":"Megiddo, N., Zemel, E., Hakimi, S.L.: The maximum coverage location problem. SIAM J. Algebraic Discrete Methods 4(2), 253\u2013261 (1983)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"issue":"1","key":"1177_CR14","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF01942293","volume":"32","author":"R Church","year":"1974","unstructured":"Church, R., Velle, C.R.: The maximal covering location problem. Pap. Reg. Sci. 32(1), 101\u2013118 (1974)","journal-title":"Pap. Reg. Sci."},{"issue":"2","key":"1177_CR15","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/mnsc.37.2.233","volume":"37","author":"H Pirkul","year":"1991","unstructured":"Pirkul, H., Schilling, D.A.: The maximal covering location problem with capacities on total workload. Manag. Sci. 37(2), 233\u2013248 (1991)","journal-title":"Manag. Sci."},{"issue":"4","key":"1177_CR16","doi-asserted-by":"publisher","first-page":"2269","DOI":"10.1109\/TIT.2014.2308258","volume":"60","author":"E Liu","year":"2014","unstructured":"Liu, E., Chong, E.K.P., Scharf, L.L.: Greedy adaptive linear compression in signal-plus-noise models. IEEE Trans. Inf. Theory 60(4), 2269\u20132280 (2014)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1177_CR17","first-page":"235","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause, A., Singh, A., Guestrin, C.: Near-Optimal sensor placements in Gaussian processes: theory, efficient algorithms and empirical studies. J. Mach. Learn. Res. 9, 235\u2013284 (2008)","journal-title":"J. Mach. Learn. Res."},{"key":"1177_CR18","unstructured":"Chen, Y., Chuah, C., Zhao, Q.: Sensor placement for maximizing lifetime per unit cost in wireless sensor networks. In: Proceedings of IEEE Military Communication Conference, pp.\u00a01097\u20131102 (2005)"},{"issue":"1","key":"1177_CR19","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1109\/JSEN.2014.2343019","volume":"15","author":"S Ragi","year":"2015","unstructured":"Ragi, S., Mittelmann, H.D., Chong, E.K.P.: Directional sensor control: heuristic approaches. IEEE Sens. J. 15(1), 374\u2013381 (2015)","journal-title":"IEEE Sens. J."},{"issue":"1","key":"1177_CR20","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(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"1177_CR21","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"ML Fisher","year":"1978","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions-II. Math. Program. Stud. 8, 73\u201387 (1978)","journal-title":"Math. Program. Stud."},{"key":"1177_CR22","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/BFb0120891","volume":"12","author":"D Hausmann","year":"1980","unstructured":"Hausmann, D., Korte, B., Jenkyns, T.A.: Worst case analysis of greedy type algorithms for independence systems. Math. Program. Stud. 12, 120\u2013131 (1980)","journal-title":"Math. Program. Stud."},{"issue":"3","key":"1177_CR23","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.: Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado\u2013Edmonds theorem. Discrete Appl. Math. 7(3), 251\u2013274 (1984)","journal-title":"Discrete Appl. Math."},{"key":"1177_CR24","first-page":"253","volume":"B23","author":"J Vondr\u00e1k","year":"2010","unstructured":"Vondr\u00e1k, J.: Submodularity and curvature: the optimal algorithm. RIMS Kokyuroku Bessatsu B23, 253\u2013266 (2010)","journal-title":"RIMS Kokyuroku Bessatsu"},{"key":"1177_CR25","doi-asserted-by":"crossref","unstructured":"Sviridenko, M., Vondr\u00e1k, J., Ward, J.: Optimal approximation for submodular and supermodular optimization with bounded curvature. In: Proceedings of 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a01134\u20131148 (2015)","DOI":"10.1137\/1.9781611973730.76"},{"key":"1177_CR26","doi-asserted-by":"crossref","unstructured":"Liu, Y., Zhang, Z., Chong, E.K.P., Pezeshki, A.: Performance bounds for the $$k$$-batch greedy strategy in optimization problems with curvature. In: Proceedings of 2016 American Control Conference, pp.\u00a07177\u20137182 (2016)","DOI":"10.1109\/ACC.2016.7526805"},{"key":"1177_CR27","first-page":"19","volume":"125","author":"DP Chandu","year":"2015","unstructured":"Chandu, D.P.: Big step greedy heuristic for maximum coverage problem. Int. J. Comput. Appl 125, 19\u201324 (2015)","journal-title":"Int. J. Comput. Appl"},{"key":"1177_CR28","first-page":"11","volume":"2570","author":"J Edmonds","year":"2003","unstructured":"Edmonds, J.: Submodular functions, matroids, and certain polyhedra. Comb. Optim. 2570, 11\u201326 (2003)","journal-title":"Comb. Optim."},{"issue":"2","key":"1177_CR29","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.: An inequality for polymatroid functions and its applications. Discrete Appl. Math. 131(2), 255\u2013281 (2003)","journal-title":"Discrete Appl. Math."},{"key":"1177_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.6028\/jres.069B.001","volume":"69B","author":"WT Tutte","year":"1965","unstructured":"Tutte, W.T.: Lecture on matroids. J. Res. Natl. Bur. Stand.-Sec. B Math. Math. Phys. 69B, 1\u201347 (1965)","journal-title":"J. Res. Natl. Bur. Stand.-Sec. B Math. Math. Phys."},{"issue":"4","key":"1177_CR31","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1287\/moor.1100.0463","volume":"35","author":"J Lee","year":"2010","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4), 795\u2013806 (2010)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"1177_CR32","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1109\/TAC.2015.2440566","volume":"61","author":"Z Zhang","year":"2016","unstructured":"Zhang, Z., Chong, E.K.P., Pezeshki, A., Moran, W.: String submodular functions with curvature constraints. IEEE Trans. Autom. Control 61(3), 601\u2013616 (2016)","journal-title":"IEEE Trans. Autom. Control"},{"key":"1177_CR33","doi-asserted-by":"crossref","unstructured":"Liu, Y., Chong, E.K.P., Pezeshki, A.: Bounding the greedy strategy in finite-horizon string optimization. In: Proceedings of 54th IEEE Conference Decision on Control, pp.\u00a03900\u20133905 (2015)","DOI":"10.1109\/CDC.2015.7402826"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10957-017-1177-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-017-1177-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-017-1177-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T13:30:46Z","timestamp":1589722246000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10957-017-1177-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,20]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["1177"],"URL":"https:\/\/doi.org\/10.1007\/s10957-017-1177-1","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"type":"print","value":"0022-3239"},{"type":"electronic","value":"1573-2878"}],"subject":[],"published":{"date-parts":[[2018,3,20]]},"assertion":[{"value":"21 February 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 September 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}