{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T01:10:32Z","timestamp":1742951432306,"version":"3.40.3"},"publisher-location":"Singapore","reference-count":24,"publisher":"Springer Nature Singapore","isbn-type":[{"type":"print","value":"9789819777976"},{"type":"electronic","value":"9789819777983"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-981-97-7798-3_20","type":"book-chapter","created":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T18:05:37Z","timestamp":1726769137000},"page":"235-246","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximation Algorithms for\u00a0k-Submodular Maximization Under the\u00a0Fair Constraints and\u00a0Size Constraints"],"prefix":"10.1007","author":[{"given":"Weijia","family":"Hu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bin","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"issue":"1","key":"20_CR1","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1177\/000271627340900103","volume":"409","author":"M Bronfenbrenner","year":"1973","unstructured":"Bronfenbrenner, M.: Equality and equity. Ann. Am. Acad. Pol. Soc. Sci. 409(1), 9\u201323 (1973)","journal-title":"Ann. Am. Acad. Pol. Soc. Sci."},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Celis, L.E., Huang, L., Vishnoi, N.K.: Multiwinner voting with fairness constraints. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. pp. 144\u2013151. IJCAI press, Stockholm, Sweden (2018)","DOI":"10.24963\/ijcai.2018\/20"},{"key":"20_CR3","unstructured":"Celis, L.E., Keswani, V., Straszak, D., Deshpande, A., Kathuria, T., Vishnoi, N.K.: Fair and diverse dpp-based data summarization. In: Proceedings of the 35th International Conference on Machine Learning. vol.\u00a080, pp. 715\u2013724. PMLR press, Stockholm, Sweden (2018)"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Dueck, D., Frey, B.J.: Non-metric affinity propagation for unsupervised image categorization. In: proceedings of the 11th International Conference on Computer Vision. pp.\u00a01\u20138. IEEE Computer Society press, Rio de Janeiro, Brazil (2007)","DOI":"10.1109\/ICCV.2007.4408853"},{"key":"20_CR5","unstructured":"Halabi, M.E., Fusco, F., Norouzi-Fard, A., Tardos, J., Tarnawski, J.: Fairness in streaming submodular maximization over a matroid constraint. In: Proceedings of the 15th International Conference on Machine Learning. vol.\u00a0202, pp. 9150\u20139171. PMLR press, Honolulu, Hawaii, USA (2023)"},{"key":"20_CR6","unstructured":"Halabi, M.E., Mitrovic, S., Norouzi-Fard, A., Tardos, J., Tarnawski, J.: Fairness in streaming submodular maximization: Algorithms and hardness. Advances in Neural Information Processing Systems abs\/2010.07431 (2020)"},{"key":"20_CR7","doi-asserted-by":"publisher","unstructured":"Huber, A., Kolmogorov, V.: Towards minimizing k-submodular functions. In: Proceedings of the 2nd International Symposium on Combinatorial Optimization. vol.\u00a07422, pp. 451\u2013462. Springer press, Athens, Greece (2012). https:\/\/doi.org\/10.1007\/978-3-642-32147-4_40","DOI":"10.1007\/978-3-642-32147-4_40"},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Iwata, S., Tanigawa, S., Yoshida, Y.: Improved approximation algorithms for k-submodular function maximization. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 404\u2013413. SIAM press, Arlington, VA, USA (2016)","DOI":"10.1137\/1.9781611974331.ch30"},{"key":"20_CR9","unstructured":"Kempe, D., Kleinberg, J.M., Tardos, \u00c9.: Maximizing the spread of influence through a social network. Theoretical Computer Science pp. 105\u2013147 (2015)"},{"key":"20_CR10","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: Human Language Technologies. pp. 510\u2013520. The Association for Computer Linguistics press, Portland, Oregon, USA (2011)"},{"key":"20_CR11","doi-asserted-by":"crossref","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Mathematical Methods of Operations Research pp. 177\u2013188 (1978)","DOI":"10.1287\/moor.3.3.177"},{"key":"20_CR12","doi-asserted-by":"crossref","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions - I. Mathematical Programming pp. 265\u2013294 (1978)","DOI":"10.1007\/BF01588971"},{"key":"20_CR13","unstructured":"Niu, S., Liu, Q., Zhou, Y., Li, M.: Fast algorithms for k-submodular maximization subject to a matroid constraint. CoRR abs\/2307.13996 (2023)"},{"key":"20_CR14","unstructured":"Ohsaka, N., Yoshida, Y.: Monotone k-submodular function maximization with size constraints. Advances in Neural Information Processing Systems 28 (2015)"},{"key":"20_CR15","unstructured":"Rafiey, A., Yoshida, Y.: Fast and private submodular and k-submodular functions maximization with matroid constraints. In: Proceedings of the 37th International Conference on Machine Learning. pp. 7887\u20137897. PMLR press, Virtual Event (2020)"},{"key":"20_CR16","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/j.disopt.2017.01.003","volume":"23","author":"S Sakaue","year":"2017","unstructured":"Sakaue, S.: On maximizing a monotone k-submodular function subject to a matroid constraint. Discret. Optim. 23, 105\u2013113 (2017)","journal-title":"Discret. Optim."},{"key":"20_CR17","unstructured":"Singh, A.P., Guillory, A., Bilmes, J.A.: On bisubmodular maximization. In: Proceedings of the 15th International Conference on Artificial Intelligence and Statistics. vol.\u00a022, pp. 1055\u20131063. JMLR press, La Palma, Canary Islands, Spain (2012)"},{"key":"20_CR18","doi-asserted-by":"publisher","unstructured":"Sun, Y., Liu, Y., Li, M.: Maximization of k-submodular function with a matroid constraint. In: Proceedings of the Theory and Applications of Models of Computation - 17th Annual Conference. vol. 13571, pp. 1\u201310. Springer press, Tianjin, China (2022). https:\/\/doi.org\/10.1007\/978-3-031-20350-3_1","DOI":"10.1007\/978-3-031-20350-3_1"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Tang, S., Yuan, J.: Group equality in adaptive submodular maximization. INFORMS Journal on Computing (2023)","DOI":"10.1016\/j.tcs.2022.11.030"},{"key":"20_CR20","doi-asserted-by":"crossref","unstructured":"Tang, S., Yuan, J., Mensah-Boateng, T.: Achieving long-term fairness in submodular maximization through randomization pp. 161\u2013173 (2023)","DOI":"10.1007\/978-3-031-46826-1_13"},{"key":"20_CR21","doi-asserted-by":"crossref","unstructured":"Wang, Y., Fabbri, F., Mathioudakis, M.: Fair and representative subset selection from data streams. In: Proceedings of the 30th Web Conference 2021. pp. 1340\u20131350. ACM press, Ljubljana, Slovenia (2021)","DOI":"10.1145\/3442381.3449799"},{"key":"20_CR22","doi-asserted-by":"crossref","unstructured":"Ward, J., Zivn\u00fd, S.: Maximizing bisubmodular and k-submodular functions. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 1468\u20131481. SIAM press, Portland, Oregon, USA (2014)","DOI":"10.1137\/1.9781611973402.108"},{"issue":"4","key":"20_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2850419","volume":"12","author":"J Ward","year":"2016","unstructured":"Ward, J., \u017divn\u1ef3, S.: Maximizing k-submodular functions and beyond. ACM Trans. Algorithms 12(4), 1\u201326 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"20_CR24","doi-asserted-by":"crossref","unstructured":"Xiao, H., Liu, Q., Zhou, Y., Li, M.: Approximation algorithms for k-submodular maximization subject to a knapsack constraint. CoRR arXiv: abs\/2306.14520 (2023)","DOI":"10.1007\/s40305-024-00539-y"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-97-7798-3_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,28]],"date-time":"2024-11-28T12:29:51Z","timestamp":1732796991000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-97-7798-3_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9789819777976","9789819777983"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-981-97-7798-3_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"19 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors declare that they have no conflict of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"AAIM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithmic Aspects in Information and Management","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Dallas, TX","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aaim2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/theory.utdallas.edu\/AAIM2024\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}