{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T02:30:06Z","timestamp":1747189806772,"version":"3.40.5"},"reference-count":20,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p> [Formula: see text]-submodular maximization is a generalization of submodular maximization, which requires us to select [Formula: see text] disjoint subsets instead of one subset. Attracted by practical values and applications, we consider [Formula: see text]-submodular maximization with two kinds of constraints. <\/jats:p><jats:p> For total size and individual size difference constraints, we present a [Formula: see text]-approximation algorithm for maximizing a nonnegative k-submodular function, running in time [Formula: see text] at worst. Specially, if [Formula: see text] is multiple of [Formula: see text], the approximation ratio can reduce to [Formula: see text], running in time [Formula: see text] at worst. Besides, this algorithm can be applied to [Formula: see text]-bisubmodular achieving [Formula: see text]-approximation running in time [Formula: see text]. Furthermore, if [Formula: see text] is multiple of 2, the approximation ratio can reduce to [Formula: see text], running in time [Formula: see text] at worst. <\/jats:p><jats:p> For individual size constraint, there is a [Formula: see text]-approximation algorithm for maximizing a nonnegative [Formula: see text]-submodular function and an nonnegative [Formula: see text]-bisubmodular function, running in time [Formula: see text] and [Formula: see text] respectively, at worst. <\/jats:p>","DOI":"10.1142\/s1793830921500361","type":"journal-article","created":{"date-parts":[[2020,10,7]],"date-time":"2020-10-07T10:59:25Z","timestamp":1602068365000},"page":"2150036","source":"Crossref","is-referenced-by-count":5,"title":["<i>k<\/i>-Submodular maximization with two kinds of constraints"],"prefix":"10.1142","volume":"13","author":[{"given":"Ganquan","family":"Shi","sequence":"first","affiliation":[{"name":"School of Mathematical Sciences, University of Science and Technology of China, Hefei 230026, P. R. China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4535-2280","authenticated-orcid":false,"given":"Shuyang","family":"Gu","sequence":"additional","affiliation":[{"name":"Department of Computer Information Systems, Texas A & M University-Central Texas, Killeen, TX 76549, USA"}]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Texas at Dallas, Richardson, TX 75080, USA"}]}],"member":"219","published-online":{"date-parts":[[2020,12,3]]},"reference":[{"key":"S1793830921500361BIB001","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.110"},{"issue":"3","key":"S1793830921500361BIB002","first-page":"32","volume":"14","author":"Buchbinder N.","year":"2018","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"S1793830921500361BIB003","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"S1793830921500361BIB004","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"S1793830921500361BIB005","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109675"},{"key":"S1793830921500361BIB006","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"S1793830921500361BIB007","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"S1793830921500361BIB008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22006-7_29"},{"key":"S1793830921500361BIB009","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32147-4_40"},{"key":"S1793830921500361BIB011","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch30"},{"key":"S1793830921500361BIB012","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"S1793830921500361BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_91"},{"key":"S1793830921500361BIB014","doi-asserted-by":"publisher","DOI":"10.1287\/opre.43.4.684"},{"key":"S1793830921500361BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"S1793830921500361BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/s11704-016-5106-5"},{"key":"S1793830921500361BIB017","first-page":"694","volume-title":"Advances in Neural Information Processing Systems","volume":"28","author":"Ohsaka N.","year":"2015"},{"key":"S1793830921500361BIB018","first-page":"88","volume-title":"Int. Workshop Combinatorial Algorithms","author":"Oshima H.","year":"2017"},{"key":"S1793830921500361BIB020","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2749263"},{"key":"S1793830921500361BIB021","first-page":"1055","volume-title":"Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics","volume":"22","author":"Singh A.","year":"2012"},{"issue":"4","key":"S1793830921500361BIB022","first-page":"47","volume":"12","author":"Ward J.","year":"2016","journal-title":"ACM Trans. Algorithms (TALG)"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830921500361","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,12]],"date-time":"2021-07-12T09:04:42Z","timestamp":1626080682000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830921500361"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,3]]},"references-count":20,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1142\/S1793830921500361"],"URL":"https:\/\/doi.org\/10.1142\/s1793830921500361","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2020,12,3]]}}}