{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T18:45:51Z","timestamp":1747853151223},"publisher-location":"Cham","reference-count":28,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319334608"},{"type":"electronic","value":"9783319334615"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-33461-5_27","type":"book-chapter","created":{"date-parts":[[2016,5,24]],"date-time":"2016-05-24T18:35:59Z","timestamp":1464114959000},"page":"325-336","source":"Crossref","is-referenced-by-count":7,"title":["Maximizing Monotone Submodular Functions over the Integer Lattice"],"prefix":"10.1007","author":[{"given":"Tasuku","family":"Soma","sequence":"first","affiliation":[]},{"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,5,25]]},"reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Gamzu, I., Tennenholtz, M.: Optimizing budget allocation among channels and influencers. In: Proceedings of WWW, pp. 381\u2013388 (2012)","DOI":"10.1145\/2187836.2187888"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., Vondr\u00e1k, J.: Fast algorithms for maximizing submodular functions. In: Proceedings of SODA, pp. 1497\u20131514 (2013)","DOI":"10.1137\/1.9781611973402.110"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: A tight linear time $$(1\/2)$$ -approximation for unconstrained submodular maximization. In: Proceedings of FOCS, pp. 649\u2013658 (2012)","DOI":"10.1109\/FOCS.2012.73"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. In: Proceedings of SODA, pp. 392\u2013403 (2016)","DOI":"10.1137\/1.9781611974331.ch29"},{"key":"27_CR5","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J.S., Schwartz, R.: Submodular maximization with cardinality constraints. In: Proceedings of SODA, pp. 1433\u20131452 (2014)","DOI":"10.1137\/1.9781611973402.106"},{"key":"27_CR6","doi-asserted-by":"crossref","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":"27_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 FOCS, pp. 575\u2013584 (2010)","DOI":"10.1109\/FOCS.2010.60"},{"key":"27_CR8","doi-asserted-by":"crossref","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. Theor. Ser. B 188, 161\u2013188 (1984)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"27_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 WWW, pp. 937\u2013948 (2014)","DOI":"10.1145\/2566486.2568039"},{"key":"27_CR10","doi-asserted-by":"crossref","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, 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"4","key":"27_CR11","doi-asserted-by":"crossref","first-page":"1133","DOI":"10.1137\/090779346","volume":"40","author":"U Feige","year":"2011","unstructured":"Feige, U., Mirrokni, V.S., Vondrak, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133\u20131153 (2011)","journal-title":"SIAM J. Comput."},{"key":"27_CR12","volume-title":"Submodular Functions and Optimization","author":"S Fujishige","year":"2005","unstructured":"Fujishige, S.: Submodular Functions and Optimization, 2nd edn. Elsevier, New York (2005)","edition":"2"},{"key":"27_CR13","doi-asserted-by":"crossref","unstructured":"Gottschalk, C., Peis, B.: Submodular function maximization on the bounded integer lattice. ArXiv preprint (2015)","DOI":"10.1007\/978-3-319-28684-6_12"},{"issue":"1","key":"27_CR14","doi-asserted-by":"crossref","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":"27_CR15","unstructured":"Iwata, S., Tanigawa, S., Yoshida, Y.: Bisubmodular function maximization and extensions. Mathematical Engineering Technical Reports (2013)"},{"key":"27_CR16","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Post, I., Vondrak, J.: Online submodular welfare maximization: Greedy is optimal. In: Proceedings of SODA, pp. 1216\u20131225 (2012)","DOI":"10.1137\/1.9781611973105.88"},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proceedings of KDD, pp. 137\u2013146 (2003)","DOI":"10.1145\/956750.956769"},{"key":"27_CR18","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 (2014)","DOI":"10.1017\/CBO9781139177801.004"},{"key":"27_CR19","unstructured":"Lin, H., Bilmes, J.: Multi-document summarization via budgeted maximization of submodular functions. In: Proceedings of NAACL, pp. 912\u2013920 (2010)"},{"key":"27_CR20","unstructured":"Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: Proceedings of NAACL, pp. 510\u2013520 (2011)"},{"key":"27_CR21","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718508","volume-title":"Discrete Convex Analysis","author":"K Murota","year":"2003","unstructured":"Murota, K.: Discrete Convex Analysis. SIAM, Philadelphia (2003)"},{"key":"27_CR22","doi-asserted-by":"crossref","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 - II. Math. Program. Studies 8, 73\u201387 (1978)","journal-title":"Math. Program. Studies"},{"issue":"1","key":"27_CR23","doi-asserted-by":"crossref","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 \u2013 a view from discrete convex analysis\u2013. Discrete Math. Algorithms Appl. 1(1), 1\u201323 (2009)","journal-title":"Discrete Math. Algorithms Appl."},{"key":"27_CR24","unstructured":"Singh, A., Guillory, A., Bilmes, J.: On bisubmodular maximization. In: Proceedings of AISTATS, pp. 1055\u20131063 (2012)"},{"key":"27_CR25","unstructured":"Soma, T., Kakimura, N., Inaba, K., Kawarabayashi, K.: Optimal budget allocation: theoretical guarantee and efficient algorithm. In: Proceedings of ICML (2014)"},{"key":"27_CR26","unstructured":"Soma, T., Yoshida, Y.: A generalization of submodular cover via the diminishing return property on the integer lattice. In: Proceedings of NIPS (2015)"},{"issue":"1","key":"27_CR27","doi-asserted-by":"crossref","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":"27_CR28","doi-asserted-by":"crossref","unstructured":"Ward, J., \u017divn\u00fd, S.: Maximizing bisubmodular and $$k$$ -submodular functions. In: Proceedings of SODA, pp. 1468\u20131481 (2014)","DOI":"10.1137\/1.9781611973402.108"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-33461-5_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,8]],"date-time":"2019-09-08T15:47:05Z","timestamp":1567957625000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-33461-5_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319334608","9783319334615"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-33461-5_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}