{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T01:46:08Z","timestamp":1767318368713,"version":"3.48.0"},"publisher-location":"Singapore","reference-count":22,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819548385","type":"print"},{"value":"9789819548392","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-981-95-4839-2_32","type":"book-chapter","created":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T01:43:33Z","timestamp":1767318213000},"page":"408-414","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Maximizing the\u00a0Difference of\u00a0DR-Submodular Function on\u00a0the\u00a0Integer Lattice"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9941-0629","authenticated-orcid":false,"given":"Jingjing","family":"Tan","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-0632-0265","authenticated-orcid":false,"given":"Cuiping","family":"Ge","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0737-1915","authenticated-orcid":false,"given":"Meixia","family":"Li","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0005-7229-4743","authenticated-orcid":false,"given":"Meng","family":"Sun","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9100-9291","authenticated-orcid":false,"given":"Ruiqi","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,1,2]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Quanrud, K.: Submodular function maximization in parallel via the multilinear relaxation. In: Proceedings of SODA, pp. 303\u2013322 (2019)","DOI":"10.1137\/1.9781611975482.20"},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"Das, A., Kempe, D.: Algorithms for subset selection in linear regression. In: Proceedings of STOC, pp. 45\u201354 (2008)","DOI":"10.1145\/1374376.1374384"},{"key":"32_CR3","unstructured":"Das, A., Kempe, D.: Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Proceedings of ICML, pp. 1057\u20131064 (2011)"},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"Ene, A., Nguyen, H.L.: Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In: Proceedings of SODA, pp. 274\u2013282 (2019)","DOI":"10.1137\/1.9781611975482.18"},{"key":"32_CR5","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. Math. Program. 14, 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"32_CR6","first-page":"65","volume":"32","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximation set cover. J. ACM 32, 65\u201382 (1998)","journal-title":"J. ACM"},{"key":"32_CR7","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":"32_CR8","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1287\/opre.1110.1000","volume":"60","author":"S He","year":"2012","unstructured":"He, S., Zhang, J., Zhang, S.: Polymatroid optimization, submodularity, and joint replenishment games. Oper. Res. 60, 128\u2013137 (2012)","journal-title":"Oper. Res."},{"key":"32_CR9","first-page":"123","volume":"2019","author":"RQ Yang","year":"2019","unstructured":"Yang, R.Q., Xu, D.C., Li, M., Xu, Y.C.: Thresholding methods for streaming submodular maximization with a cardinality constraint and its variants. Nonlinear Comb. Optim. 2019, 123\u2013140 (2019)","journal-title":"Nonlinear Comb. Optim."},{"key":"32_CR10","doi-asserted-by":"crossref","unstructured":"Yang, R.Q., Xu, D.C., Du, D.L., Xu, Y.C., Yan, X.H.: Maximization of constrained non-submodular functions. In: Proceedings of COCOON, pp. 615\u2013626 (2019)","DOI":"10.1007\/978-3-030-26176-4_51"},{"key":"32_CR11","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s10898-021-01014-1","volume":"80","author":"ZZ Zhang","year":"2021","unstructured":"Zhang, Z.Z., Du, D.L., Jiang, Y.J., Wu, C.C.: Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint. J. Global Optim. 80, 595\u2013616 (2021)","journal-title":"J. Global Optim."},{"key":"32_CR12","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.: Maximization monotone submodular functions over the integer lattice. Math. Program. 172, 539\u2013563 (2018)","journal-title":"Math. Program."},{"key":"32_CR13","doi-asserted-by":"crossref","unstructured":"Kapralov, M., Post, I., Vondr\u00e1k, J.: Online submodular welfare maximization: greedy is optimal. In: Proceedings of SODA, pp. 1216\u20131225 (2012)","DOI":"10.1137\/1.9781611973105.88"},{"key":"32_CR14","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":"32_CR15","unstructured":"Khanna, R., Elenberg, E.R., Dimakis, A.G., Negahban S., Ghosh J.: Scalable greedy feature selection via weak submodularity. In: Proceedings of ICAIS, pp. 1560\u20131568 (2017)"},{"key":"32_CR16","unstructured":"Kuhnle, A., Smith, J.D., Crawford, V.G., Thai, M.T.: Fast maximization of non-submodular, monotonic functions on the integer lattice. In: Proceedings of ICML, pp. 2791\u20132800 (2018)"},{"issue":"2","key":"32_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10878-023-00986-y","volume":"45","author":"J Tan","year":"2023","unstructured":"Tan, J., Xu, Y., Zhang, D., Zhang, X.: On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice. J. Comb. Optim. 45(2), 1\u201319 (2023)","journal-title":"J. Comb. Optim."},{"key":"32_CR18","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 SODA, pp. 1134\u20131148 (2015)","DOI":"10.1137\/1.9781611973730.76"},{"key":"32_CR19","unstructured":"Iyer, R., Bilmes, J.: Algorithms for approximate minimization of the difference between submodular functions, with applications. In: Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, pp. 407\u2013417 (2012)"},{"key":"32_CR20","unstructured":"Narasimhan, M., Bilmes, J.A.: A submodular-supermodular procedure with applications to discriminative structure learning. arXiv preprint arXiv:1207.1404 (2012)"},{"key":"32_CR21","doi-asserted-by":"publisher","first-page":"2946","DOI":"10.1007\/s10878-021-00827-w","volume":"44","author":"YJ Wang","year":"2022","unstructured":"Wang, Y.J., Xu, D.C., Du, D.L., Jiang, Y.J.: Bicriteria streaming algorithms to balance gain and cost with cardinality constraint. J. Comb. Optim. 44, 2946\u20132962 (2022)","journal-title":"J. Comb. Optim."},{"key":"32_CR22","doi-asserted-by":"publisher","first-page":"1643","DOI":"10.1007\/s11590-023-01979-w","volume":"17","author":"C Lu","year":"2023","unstructured":"Lu, C., Yang, W.G., Gao, S.X.: Streaming algorithms for maximizing the? Difference of submodular functions and the sum of submodular and supermodular functions. Optim. Lett. 17, 1643\u20131667 (2023)","journal-title":"Optim. Lett."}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-4839-2_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T01:43:36Z","timestamp":1767318216000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-4839-2_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9789819548385","9789819548392"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-4839-2_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"2 January 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TAMC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual Conference on Theory and Applications of Models of Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Jinan","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 September 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tamc2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.maths.sdnu.edu.cn\/TAMC2025.htm","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}