{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:21Z","timestamp":1740109281542,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,2,4]],"date-time":"2021-02-04T00:00:00Z","timestamp":1612396800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,4]],"date-time":"2021-02-04T00:00:00Z","timestamp":1612396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["19K20219"],"award-info":[{"award-number":["19K20219"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP19J22607"],"award-info":[{"award-number":["JP19J22607"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,7]]},"DOI":"10.1007\/s10107-021-01620-7","type":"journal-article","created":{"date-parts":[[2021,2,4]],"date-time":"2021-02-04T13:22:13Z","timestamp":1612444933000},"page":"85-119","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice"],"prefix":"10.1007","volume":"194","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2101-1484","authenticated-orcid":false,"given":"Takanori","family":"Maehara","sequence":"first","affiliation":[]},{"given":"So","family":"Nakashima","sequence":"additional","affiliation":[]},{"given":"Yutaro","family":"Yamaguchi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,4]]},"reference":[{"issue":"7\u20138","key":"1620_CR1","doi-asserted-by":"publisher","first-page":"811","DOI":"10.1177\/0278364904045468","volume":"23","author":"A Abrams","year":"2004","unstructured":"Abrams, A., Ghrist, R.: State complexes for metamorphic robots. Int. J. Robot. Res. 23(7\u20138), 811\u2013826 (2004). https:\/\/doi.org\/10.1177\/0278364904045468","journal-title":"Int. J. Robot. Res."},{"issue":"3","key":"1620_CR2","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1023\/B:JOCO.0000038913.96607.c2","volume":"8","author":"AA Ageev","year":"2004","unstructured":"Ageev, A.A., Sviridenko, M.I.: Pipage rounding: a new method of constructing algorithms with proven performance guarantee. J. Comb. Optim. 8(3), 307\u2013328 (2004)","journal-title":"J. Comb. Optim."},{"key":"1620_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N., Gamzu, I., Tennenholtz, M.: Optimizing budget allocation among channels and influencers. In: Proceedings of the 21st International Conference on World Wide Web (WWW\u201912), pp. 381\u2013388. ACM (2012)","DOI":"10.1145\/2187836.2187888"},{"key":"1620_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1090\/conm\/453\/08795","volume":"453","author":"HJ Bandelt","year":"2008","unstructured":"Bandelt, H.J., Chepoi, V.: Metric graph theory and geometry: a survey. Contemp. Math. 453, 49\u201386 (2008)","journal-title":"Contemp. Math."},{"issue":"1","key":"1620_CR5","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/aama.1998.0583","volume":"21","author":"M Barnabei","year":"1998","unstructured":"Barnabei, M., Nicoletti, G., Pezzoli, L.: Matroids on partially ordered sets. Adv. Appl. Math. 21(1), 78\u2013112 (1998)","journal-title":"Adv. Appl. Math."},{"issue":"4","key":"1620_CR6","doi-asserted-by":"publisher","first-page":"2277","DOI":"10.2140\/agt.2010.10.2277","volume":"10","author":"T Brady","year":"2010","unstructured":"Brady, T., McCammond, J.: Braids, posets and orthoschemes. Algebraic Geom. Topol. 10(4), 2277\u20132314 (2010). https:\/\/doi.org\/10.2140\/agt.2010.10.2277","journal-title":"Algebraic Geom. Topol."},{"key":"1620_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-12494-9","volume-title":"Metric Spaces of Non-positive Curvature","author":"MR Bridson","year":"1999","unstructured":"Bridson, M.R., Haefliger, A.: Metric Spaces of Non-positive Curvature. Springer, Berlin (1999)"},{"issue":"6","key":"1620_CR8","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\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"key":"1620_CR9","unstructured":"Chalopin, J., Chepoi, V., Hirai, H., Osajda, D.: Weakly modular graphs and nonpositive curvature. arXiv e-prints arXiv:1409.3892 (2014)"},{"issue":"6","key":"1620_CR10","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":"1620_CR11","doi-asserted-by":"publisher","unstructured":"Chepoi, V.: Graphs of some cat(0) complexes. Adv. Appl. Math. 24(2), 125\u2013179 (2000). https:\/\/doi.org\/10.1006\/aama.1999.0677. http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0196885899906772","DOI":"10.1006\/aama.1999.0677"},{"issue":"3","key":"1620_CR12","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-edmonds theorem. Discrete Appl. Math. 7(3), 251\u2013274 (1984)","journal-title":"Discrete Appl. Math."},{"key":"1620_CR13","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G Cornnejols","year":"1977","unstructured":"Cornnejols, G., Fisher, M., Nemhauser, G.: Location of bank accounts of optimize float: an analytic study of exact and approximate algorithm. Manag. Sci. 23, 789\u2013810 (1977)","journal-title":"Manag. Sci."},{"key":"1620_CR14","unstructured":"Ene, A., Nguyen, H.L.: A reduction for optimizing lattice submodular functions with diminishing returns. arXiv preprint arXiv:1606.08362 (2016)"},{"issue":"4","key":"1620_CR15","first-page":"309","volume":"26","author":"S Fujishige","year":"1983","unstructured":"Fujishige, S., Tomizawa, N.: A note on submodular functions on distributive lattices. J. Oper. Res. Soc. Jpn. 26(4), 309\u2013318 (1983)","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"1620_CR16","doi-asserted-by":"crossref","unstructured":"Ghosh, B.K.: Probability inequalities related to markov\u2019s theorem. Am. Stat. 56(3), 186\u2013190 (2002). http:\/\/www.jstor.org\/stable\/3087296","DOI":"10.1198\/000313002119"},{"key":"1620_CR17","doi-asserted-by":"crossref","unstructured":"Gottschalk, C., Peis, B.: Submodular function maximization over distributive and integer lattices. arXiv preprint arXiv:1505.05423 (2015)","DOI":"10.1007\/978-3-319-28684-6_12"},{"key":"1620_CR18","volume-title":"General Lattice Theory","author":"G Gr\u00e4tzer","year":"2002","unstructured":"Gr\u00e4tzer, G.: General Lattice Theory. Springer, New York (2002)"},{"key":"1620_CR19","unstructured":"Hassani, H., Soltanolkotabi, M., Karbasi, A.: Gradient methods for submodular maximization. In: Advances in Neural Information Processing Systems (NIPS\u201917), pp. 5841\u20135851 (2017)"},{"issue":"1","key":"1620_CR20","first-page":"71","volume":"61","author":"H Hirai","year":"2018","unstructured":"Hirai, H.: L-convexity on graph structures. J. Oper. Res. Soc. Jpn. 61(1), 71\u2013109 (2018)","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"1620_CR21","doi-asserted-by":"crossref","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963). http:\/\/www.jstor.org\/stable\/2282952","DOI":"10.1080\/01621459.1963.10500830"},{"key":"1620_CR22","doi-asserted-by":"crossref","unstructured":"Krause, A., Golovin, D.: Submodular function maximization. In: Tractability: Practical Approaches to Hard Problems, pp. 71\u2013104. Cambridge University Press, Cambridge (2014)","DOI":"10.1017\/CBO9781139177801.004"},{"key":"1620_CR23","doi-asserted-by":"crossref","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear constraints. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201909), pp. 545\u2013554 (2009). http:\/\/dl.acm.org\/citation.cfm?id=1496770.1496830","DOI":"10.1137\/1.9781611973068.60"},{"key":"1620_CR24","unstructured":"Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics (ACL\u201911), pp. 510\u2013520 (2011)"},{"key":"1620_CR25","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Submodular functions and convexity. In: Mathematical Programming The State of the Art, pp. 235\u2013257. Springer, New York (1983)","DOI":"10.1007\/978-3-642-68874-4_10"},{"key":"1620_CR26","unstructured":"Maehara, T., Nakashima, S.: Rank axiom of modular supermatroids: a connection with directional DR submodular functions (2020)"},{"issue":"1","key":"1620_CR27","first-page":"151","volume":"1","author":"K Murota","year":"2016","unstructured":"Murota, K., et al.: Discrete convex analysis: a tool for economics and game theory. J. Mech. Inst. Des. 1(1), 151\u2013273 (2016)","journal-title":"J. Mech. Inst. Des."},{"key":"1620_CR28","doi-asserted-by":"crossref","unstructured":"Nakashima, S., Maehara, T.: Subspace selection via DR-submodular maximization on lattices. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI\u201919), pp. 4618\u20134625 (2019). https:\/\/www.aaai.org\/Papers\/AAAI\/2019\/AAAI-MaeharaT2.2673.pdf","DOI":"10.1609\/aaai.v33i01.33014618"},{"issue":"1","key":"1620_CR29","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":"1620_CR30","unstructured":"Roller, M.: POC sets, median algebras and group actions, an extended study of Dunwoody\u2019s construction and Sageev\u2019 theorem. University of Southampton, Technical report (1998)"},{"key":"1620_CR31","doi-asserted-by":"crossref","unstructured":"Shamaiah, M., Banerjee, S., Vikalo, H.: Greedy sensor selection: leveraging submodularity. In: Proceedings of the 49th IEEE Conference on Decision and Control (CDC\u201910), pp. 2572\u20132577 (2010)","DOI":"10.1109\/CDC.2010.5717225"},{"issue":"1\u20132","key":"1620_CR32","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1007\/s10107-018-1324-y","volume":"172","author":"T Soma","year":"2018","unstructured":"Soma, T., Yoshida, Y.: Maximizing monotone submodular functions over the integer lattice. Math. Program. 172(1\u20132), 539\u2013563 (2018)","journal-title":"Math. Program."},{"issue":"1","key":"1620_CR33","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"1620_CR34","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1287\/opre.26.2.305","volume":"26","author":"DM Topkis","year":"1978","unstructured":"Topkis, D.M.: Minimizing a submodular function on a lattice. Oper. Res. 26(2), 305\u2013321 (1978)","journal-title":"Oper. Res."},{"key":"1620_CR35","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC\u201908), pp. 67\u201374. ACM (2008)","DOI":"10.1145\/1374376.1374389"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01620-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01620-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01620-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T19:04:05Z","timestamp":1656356645000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01620-7"}},"subtitle":["\u2014 Continuous Greedy Algorithm on Median Complex \u2014"],"short-title":[],"issued":{"date-parts":[[2021,2,4]]},"references-count":35,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["1620"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01620-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2021,2,4]]},"assertion":[{"value":"20 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"No conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}