{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T11:14:12Z","timestamp":1772882052620,"version":"3.50.1"},"reference-count":16,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2020,2]]},"abstract":"<jats:p> We study the problem of maximizing non-monotone diminish return (DR)-submodular function on the bounded integer lattice, which is a generalization of submodular set function. DR-submodular functions consider the case that we can choose multiple copies for each element in the ground set. This generalization has many applications in machine learning. In this paper, we propose a [Formula: see text]-approximation algorithm with a running time of [Formula: see text], where [Formula: see text] is the size of the ground set, [Formula: see text] is the upper bound of integer lattice. Discovering important properties of DR-submodular function, we propose a fast double greedy algorithm which improves the running time. <\/jats:p>","DOI":"10.1142\/s179383092050007x","type":"journal-article","created":{"date-parts":[[2019,10,29]],"date-time":"2019-10-29T23:38:04Z","timestamp":1572392284000},"page":"2050007","source":"Crossref","is-referenced-by-count":8,"title":["A fast double greedy algorithm for non-monotone DR-submodular function maximization"],"prefix":"10.1142","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4535-2280","authenticated-orcid":false,"given":"Shuyang","family":"Gu","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Texas at Dallas, 800 W Campbell Rd, Richardson, Texas 75080, USA"}]},{"given":"Ganquan","family":"Shi","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Shanghai Key Laboratory of PMMP, East China Normal University, Shanghai 200241, P. R. China"}]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Texas at Dallas, 800 W Campbell Rd, Richardson, Texas 75080, USA"}]},{"given":"Changhong","family":"Lu","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Shanghai Key Laboratory of PMMP, East China Normal University, Shanghai 200241, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2019,12,19]]},"reference":[{"key":"S179383092050007XBIB001","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.110"},{"key":"S179383092050007XBIB003","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.106"},{"key":"S179383092050007XBIB004","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"issue":"3","key":"S179383092050007XBIB005","first-page":"32","volume":"14","author":"Buchbinder N.","year":"2018","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"S179383092050007XBIB006","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"S179383092050007XBIB008","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"S179383092050007XBIB009","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.83"},{"key":"S179383092050007XBIB010","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-28684-6_12"},{"key":"S179383092050007XBIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2008.05.002"},{"key":"S179383092050007XBIB012","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"S179383092050007XBIB013","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"S179383092050007XBIB014","first-page":"351","volume-title":"Int. Conf. Machine Learning","author":"Soma T.","year":"2014"},{"key":"S179383092050007XBIB015","first-page":"847","volume-title":"Advances in Neural Information Processing Systems","author":"Soma T.","year":"2015"},{"key":"S179383092050007XBIB016","volume-title":"31st AAAI Conf. Artificial Intelligence","author":"Soma T.","year":"2017"},{"key":"S179383092050007XBIB017","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1324-y"},{"key":"S179383092050007XBIB018","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S179383092050007X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,17]],"date-time":"2020-02-17T21:34:16Z","timestamp":1581975256000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S179383092050007X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,19]]},"references-count":16,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2020,2]]}},"alternative-id":["10.1142\/S179383092050007X"],"URL":"https:\/\/doi.org\/10.1142\/s179383092050007x","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,19]]}}}