{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:05:14Z","timestamp":1753880714959,"version":"3.41.2"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:p> The problem of maximization submodular functions with a cardinality constraint has been extensively researched in recent years. Balkanski and Singer were the first to study this class problem. Subsequently, Chekuri and Kent recently extended these results to more general constraints, that is, [Formula: see text]-cardinality constraint, partition and laminar matroids, matching, knapsack constraints, and including their intersection. They proposed a [Formula: see text] approximation randomized-parallel-greedy algorithm which are poly-logarithmic adaptivity. However, these existing approaches are hardly extended to the nonsubmodular case. In this paper, we investigate the problem of maximization on a nonsubmodular function subject to a cardinality constraint, provided the objective function is specified by a generic submodularity ratio [Formula: see text]. We design a [Formula: see text]-approximation Greedy algorithm by using the technical aspects to maximize the multilinear relaxation of the object function under the [Formula: see text]-cardinality constraints. The adaptive of multilinear relaxation is [Formula: see text]; the number of oracle is [Formula: see text]. <\/jats:p>","DOI":"10.1142\/s0217595921400091","type":"journal-article","created":{"date-parts":[[2021,2,27]],"date-time":"2021-02-27T00:56:36Z","timestamp":1614387396000},"source":"Crossref","is-referenced-by-count":0,"title":["Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint"],"prefix":"10.1142","volume":"38","author":[{"given":"Jingjing","family":"Tan","sequence":"first","affiliation":[{"name":"School of Mathematics and Information Science, Weifang University, Weifang Shandong, 261061, P. R. China"}]},{"given":"Wenting","family":"Chen","sequence":"additional","affiliation":[{"name":"School of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao Shandong 266590, P. R. China"}]},{"given":"Meixia","family":"Li","sequence":"additional","affiliation":[{"name":"School of Mathematics and Information Science, Weifang University, Weifang Shandong, 261061, P. R. China"}]},{"given":"Wenchao","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao Shandong 266590, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2021,3,22]]},"reference":[{"key":"S0217595921400091BIB001","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1016\/j.endm.2010.05.086","volume":"36","author":"Bouhtou M","year":"2010","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"S0217595921400091BIB002","first-page":"1138","volume-title":"Proceedings of STOC","author":"Balkanski E","year":"2018"},{"key":"S0217595921400091BIB003","first-page":"283","volume-title":"Proceedings of SODA","author":"Balkanski E","year":"2019"},{"key":"S0217595921400091BIB004","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"S0217595921400091BIB005","first-page":"201","volume-title":"Proceedings of CITCS","author":"Chekuri C","year":"2015"},{"key":"S0217595921400091BIB006","first-page":"303","volume-title":"Proceedings of SODA","author":"Chekuri C","year":"2019"},{"key":"S0217595921400091BIB007","first-page":"45","volume-title":"Proceedings of STC","author":"Das A","year":"2008"},{"key":"S0217595921400091BIB008","first-page":"1057","volume-title":"Proceedings of ICML","author":"Das A","year":"2011"},{"key":"S0217595921400091BIB009","first-page":"439","volume-title":"Proceedings of ICKDDM","author":"EI-Arini K","year":"2011"},{"key":"S0217595921400091BIB010","first-page":"274","volume-title":"Proceedings of SODA","author":"Ene A","year":"2019"},{"key":"S0217595921400091BIB011","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"S0217595921400091BIB012","doi-asserted-by":"crossref","first-page":"833","DOI":"10.1007\/s10898-019-00800-2","volume":"75","author":"Gong S","year":"2019","journal-title":"Journal of Global Optimization"},{"key":"S0217595921400091BIB013","first-page":"189","volume-title":"Proceedings of ICWWW","author":"Hartling J","year":"2008"},{"key":"S0217595921400091BIB014","first-page":"1897","volume-title":"Proceedings of CVPR","author":"Jegelka S","year":"2011"},{"issue":"5","key":"S0217595921400091BIB015","doi-asserted-by":"crossref","first-page":"1235","DOI":"10.1007\/s11590-019-01430-z","volume":"14","author":"Jiang YJ","year":"2020","journal-title":"Optimization Letters"},{"key":"S0217595921400091BIB016","first-page":"1358","volume-title":"Proceedings of ICML","author":"Mirzasoleiman B","year":"2016"},{"key":"S0217595921400091BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"S0217595921400091BIB018","first-page":"86","volume-title":"Proceedings of SIAM","author":"Neal EY","year":"2000"},{"key":"S0217595921400091BIB019","first-page":"1","volume-title":"Proceedings of ICCV","author":"Simon I","year":"2007"},{"key":"S0217595921400091BIB020","first-page":"67","volume-title":"Proceedings of STOC","author":"Vondr\u00e1k J","year":"2008"},{"issue":"4","key":"S0217595921400091BIB021","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1007\/s10898-019-00840-8","volume":"76","author":"Wang YJ","year":"2020","journal-title":"Journal of Global Optimization"},{"issue":"4","key":"S0217595921400091BIB022","doi-asserted-by":"crossref","first-page":"1950022","DOI":"10.1142\/S0217595919500222","volume":"36","author":"Yang RQ","year":"2019","journal-title":"Asia Pacific journal of Operational Research"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595921400091","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T09:04:09Z","timestamp":1633943049000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0217595921400091"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,22]]},"references-count":22,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["10.1142\/S0217595921400091"],"URL":"https:\/\/doi.org\/10.1142\/s0217595921400091","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"type":"print","value":"0217-5959"},{"type":"electronic","value":"1793-7019"}],"subject":[],"published":{"date-parts":[[2021,3,22]]},"article-number":"2140009"}}