{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T01:17:09Z","timestamp":1769908629748,"version":"3.49.0"},"reference-count":27,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2019,12]]},"abstract":"<jats:p> We consider the problem of maximizing monotone submodular function over the bounded integer lattice with a cardinality constraint. Function [Formula: see text] is submodular over integer lattice if [Formula: see text], [Formula: see text], where \u2228 and \u2227 represent elementwise maximum and minimum, respectively. Let [Formula: see text], and [Formula: see text], we study the problem of maximizing submodular function [Formula: see text] with constraints [Formula: see text] and [Formula: see text]. A random greedy [Formula: see text]-approximation algorithm and a deterministic [Formula: see text]-approximation algorithm are proposed in this paper. Both algorithms work in value oracle model. In the random greedy algorithm, we assume the monotone submodular function satisfies diminishing return property, which is not an equivalent definition of submodularity on integer lattice. Additionally, our random greedy algorithm makes [Formula: see text] value oracle queries and deterministic algorithm makes [Formula: see text] value oracle queries. <\/jats:p>","DOI":"10.1142\/s1793830919500757","type":"journal-article","created":{"date-parts":[[2019,10,7]],"date-time":"2019-10-07T08:23:39Z","timestamp":1570436619000},"page":"1950075","source":"Crossref","is-referenced-by-count":6,"title":["Monotone submodular maximization over the bounded integer lattice with cardinality constraints"],"prefix":"10.1142","volume":"11","author":[{"given":"Lei","family":"Lai","sequence":"first","affiliation":[{"name":"Shanghai Key Laboratory of PMMP, School of Mathematical Sciences, East China Normal University, Shanghai 200241, P. R. China"}]},{"given":"Qiufen","family":"Ni","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan 430070, P. R. China"}]},{"given":"Changhong","family":"Lu","sequence":"additional","affiliation":[{"name":"Shanghai Key Laboratory of PMMP, School of Mathematical Sciences, East China Normal University, Shanghai 200241, P. R. China"}]},{"given":"Chuanhe","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan 430070, P. R. China"}]},{"given":"Weili","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Dallas, TX 75080, USA"}]}],"member":"219","published-online":{"date-parts":[[2019,12,19]]},"reference":[{"key":"S1793830919500757BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0298-1"},{"key":"S1793830919500757BIB002","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.110"},{"issue":"3","key":"S1793830919500757BIB003","first-page":"32","volume":"14","author":"Buchbinder N.","year":"2018","journal-title":"ACM Trans. Algorithms (TALG)"},{"key":"S1793830919500757BIB004","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.16"},{"key":"S1793830919500757BIB005","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.106"},{"key":"S1793830919500757BIB006","doi-asserted-by":"publisher","DOI":"10.1137\/130929205"},{"key":"S1793830919500757BIB007","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"S1793830919500757BIB008","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.60"},{"key":"S1793830919500757BIB009","volume-title":"Proc. Conf. Experiences and Perspectives of the Application of Mathematical Methods and Electronic Computers in Planning","author":"Cherenin V.","year":"1962"},{"key":"S1793830919500757BIB010","volume-title":"46th Int. Colloquium on Automata, Languages, and Programming (ICALP 2019)","author":"Ene A.","year":"2019"},{"key":"S1793830919500757BIB011","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"S1793830919500757BIB012","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.46"},{"key":"S1793830919500757BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22006-7_29"},{"key":"S1793830919500757BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"S1793830919500757BIB015","volume-title":"Submodular Functions and Optimization","volume":"58","author":"Fujishige S.","year":"2005"},{"key":"S1793830919500757BIB016","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.83"},{"key":"S1793830919500757BIB017","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-004-5909-z"},{"key":"S1793830919500757BIB018","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.45.11.1539"},{"key":"S1793830919500757BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-28684-6_12"},{"key":"S1793830919500757BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0084-2"},{"key":"S1793830919500757BIB024","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00205-7"},{"key":"S1793830919500757BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0006528"},{"key":"S1793830919500757BIB026","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"S1793830919500757BIB027","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"S1793830919500757BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2018.11.002"},{"key":"S1793830919500757BIB029","first-page":"351","volume-title":"Int. Conf. Machine Learning","author":"Soma T.","year":"2014"},{"key":"S1793830919500757BIB030","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1324-y"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830919500757","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,20]],"date-time":"2019-12-20T06:44:09Z","timestamp":1576824249000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830919500757"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12]]},"references-count":27,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2019,12]]}},"alternative-id":["10.1142\/S1793830919500757"],"URL":"https:\/\/doi.org\/10.1142\/s1793830919500757","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12]]}}}