{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,25]],"date-time":"2026-03-25T02:33:38Z","timestamp":1774406018386,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1-2","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"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"name":"JSPS Grant-in-Aid for Young Scientists","award":["26730009"],"award-info":[{"award-number":["26730009"]}]},{"name":"MEXT Grant-in-Aid for Scientific Research on Innovative Areas","award":["24106003"],"award-info":[{"award-number":["24106003"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s10107-018-1324-y","type":"journal-article","created":{"date-parts":[[2018,8,29]],"date-time":"2018-08-29T21:02:48Z","timestamp":1535576568000},"page":"539-563","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":72,"title":["Maximizing monotone submodular functions over the integer lattice"],"prefix":"10.1007","volume":"172","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9519-2487","authenticated-orcid":false,"given":"Tasuku","family":"Soma","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8919-8479","authenticated-orcid":false,"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,29]]},"reference":[{"key":"1324_CR1","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), pp. 381\u2013388 (2012)","DOI":"10.1145\/2187836.2187888"},{"key":"1324_CR2","first-page":"1497","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Ashwinkumar Badanidiyuru","year":"2013","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1497\u20131514 (2013)"},{"key":"1324_CR3","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 392\u2013403 (2015)","DOI":"10.1137\/1.9781611974331.ch29"},{"key":"1324_CR4","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: A tight linear time $$(1\/2)$$ ( 1 \/ 2 ) -approximation for unconstrained submodular maximization. In: Proceedings of the IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 649\u2013658 (2012)","DOI":"10.1109\/FOCS.2012.73"},{"key":"1324_CR5","first-page":"1433","volume-title":"Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Niv Buchbinder","year":"2013","unstructured":"Buchbinder, N., Feldman, M., Naor, J.S., Schwartz, R.: Submodular maximization with cardinality constraints. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1433\u20131452 (2014)"},{"key":"1324_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, 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"key":"1324_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Dependent randomized rounding via exchange properties of combinatorial structures. In: Proceedings of IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 575\u2013584 (2010)","DOI":"10.1109\/FOCS.2010.60"},{"key":"1324_CR8","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0095-8956(84)90023-6","volume":"188","author":"WH Cunningham","year":"1984","unstructured":"Cunningham, W.H.: Testing membership in matroid polyhedra. J. Comb. Theory Ser. B 188, 161\u2013188 (1984)","journal-title":"J. Comb. Theory Ser. B"},{"key":"1324_CR9","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Hajiaghayi, M., Mahini, H., Malec, D.L., Raghavan, S., Sawant, A., Zadimoghadam, M.: How to influence people with partial incentives. In: Proceedings of the 23rd International World Wide Web Conference, pp. 937\u2013948 (2014)","DOI":"10.1145\/2566486.2568039"},{"key":"1324_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$$ ln n for approximating set cover. J. ACM 45, 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"4","key":"1324_CR11","doi-asserted-by":"publisher","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"key":"1324_CR12","volume-title":"Submodular Functions and Optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Elsevier, Amsterdam (2005)","edition":"2"},{"key":"1324_CR13","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-319-28684-6_12","volume-title":"Approximation and Online Algorithms","author":"Corinna Gottschalk","year":"2015","unstructured":"Gottschalk, C., Peis, B.: Submodular function maximization on the bounded integer lattice. In: Approximation and Online Algorithms: 13th International Workshop, WAOA 2015, Patras, Greece, 17\u201318 Sept 2015. Revised Selected Papers, pp. 133\u2013144 (2015)"},{"issue":"1","key":"1324_CR14","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s10107-006-0084-2","volume":"112","author":"S Iwata","year":"2007","unstructured":"Iwata, S.: Submodular function minimization. Math. Program. 112(1), 45\u201364 (2007)","journal-title":"Math. Program."},{"key":"1324_CR15","doi-asserted-by":"crossref","unstructured":"Iwata, S., Tanigawa, S.I., Yoshida, Y.: Improved approximation algorithms for $$k$$ k -submodular function maximization. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 404\u2013413. Society for Industrial and Applied Mathematics, Philadelphia, PA (2016)","DOI":"10.1137\/1.9781611974331.ch30"},{"key":"1324_CR16","doi-asserted-by":"publisher","first-page":"1216","DOI":"10.1137\/1.9781611973105.88","volume-title":"Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Michael Kapralov","year":"2013","unstructured":"Kapralov, M., Post, I., Vondr\u00e1k, J.: Online submodular welfare maximization: Greedy is optimal. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1216\u20131225 (2012)"},{"key":"1324_CR17","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137\u2013146 (2003)","DOI":"10.1145\/956750.956769"},{"key":"1324_CR18","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1017\/CBO9781139177801.004","volume-title":"Tractability: Practical Approaches to Hard Problems","author":"A Krause","year":"2014","unstructured":"Krause, A., Golovin, D.: Submodular function maximization. In: Bordeaux, L., Hamadi, Y., Kohli, P. (eds.) Tractability: Practical Approaches to Hard Problems, pp. 71\u2013104. Cambridge University Press, Cambridge (2014)"},{"key":"1324_CR19","unstructured":"Lin, H., Bilmes, J.: Multi-document summarization via budgeted maximization of submodular functions. In: Proceedings of the 11th Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 912\u2013920 (2010)"},{"key":"1324_CR20","unstructured":"Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: Proceedings of the 12th Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 510\u2013520 (2011)"},{"key":"1324_CR21","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718508","volume-title":"Discrete Convex Analysis","author":"K Murota","year":"2003","unstructured":"Murota, K.: Discrete Convex Analysis. Society for Industrial and Applied Mathematics, Philadelphia (2003)"},{"key":"1324_CR22","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0121195","volume":"8","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions\u2014II. Math. Program. Stud. 8, 73\u201387 (1978)","journal-title":"Math. Program. Stud."},{"key":"1324_CR23","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"1996","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1996)"},{"issue":"1","key":"1324_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S1793830909000063","volume":"1","author":"A Shioura","year":"2009","unstructured":"Shioura, A.: On the pipage rounding algorithm for submodular function maximization\u2014a view from discrete convex analysis. Discrete Math. Algorithms Appl. 1(1), 1\u201323 (2009)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"1324_CR25","unstructured":"Singh, A., Guillory, A., Bilmes, J.: On bisubmodular maximization. In: Proceedings of the 15th International Conference on Artificial Intelligence and Statistics, pp. 1055\u20131063 (2012)"},{"key":"1324_CR26","unstructured":"Soma, T., Kakimura, N., Inaba, K., Kawarabayashi, K.: Optimal budget allocation: theoretical guarantee and efficient algorithm. In: Proceedings of the 31st International Conference on Machine Learning (ICML) (2014)"},{"key":"1324_CR27","unstructured":"Soma, T., Yoshida, Y.: A generalization of submodular cover via the diminishing return property on the integer lattice. In: Advances in Neural Information Processing Systems (NIPS) (2015)"},{"key":"1324_CR28","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/978-3-319-33461-5_27","volume-title":"Integer Programming and Combinatorial Optimization","author":"Tasuku Soma","year":"2016","unstructured":"Soma, T., Yoshida, Y.: Maximizing monotone submodular functions over the integer lattice. In: the Proceedings of the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 325\u2013336 (2016)"},{"issue":"1","key":"1324_CR29","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."},{"key":"1324_CR30","doi-asserted-by":"crossref","unstructured":"Ward, J., \u017divn\u00fd, S.: Maximizing bisubmodular and $$k$$ k -submodular functions. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1468\u20131481 (2014)","DOI":"10.1137\/1.9781611973402.108"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-018-1324-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1324-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1324-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,4]],"date-time":"2023-09-04T17:49:21Z","timestamp":1693849761000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-018-1324-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,29]]},"references-count":30,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["1324"],"URL":"https:\/\/doi.org\/10.1007\/s10107-018-1324-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,29]]},"assertion":[{"value":"29 April 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 August 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}