{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:59:16Z","timestamp":1753883956786,"version":"3.41.2"},"reference-count":23,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["12271259","12131003","11971349"],"award-info":[{"award-number":["12271259","12131003","11971349"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","award":["06446"],"award-info":[{"award-number":["06446"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Asia Pac. J. Oper. Res."],"published-print":{"date-parts":[[2023,10]]},"abstract":"<jats:p> The set cover problem has been studied extensively for many years. Submodular function plays a key role in combinatorial optimization. Extending the set cover problem, we consider three submodular cover problems. The first two problems minimize linear and submodular functions, respectively, subject to the same non-submodular cover constraint. The third problem minimizes a submodular function subject to non-submodular cover and precedence constraints. Based on the concepts of submodular ratio and gap, and Lov\u00e1sz extension, we devise greedy and primal\u2013dual approximation algorithms for these problems. <\/jats:p>","DOI":"10.1142\/s0217595923400122","type":"journal-article","created":{"date-parts":[[2023,3,23]],"date-time":"2023-03-23T15:03:58Z","timestamp":1679583838000},"source":"Crossref","is-referenced-by-count":0,"title":["Minimization Problems with Non-Submodular Cover Constraint"],"prefix":"10.1142","volume":"40","author":[{"given":"Wenqi","family":"Wang","sequence":"first","affiliation":[{"name":"School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Nanjing 210023, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhicheng","family":"Liu","sequence":"additional","affiliation":[{"name":"Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[{"name":"Faculty of Management, University of New Brunswick, Fredericton, New Brunswick, Canada E3B9Y2, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peihao","family":"Shi","sequence":"additional","affiliation":[{"name":"Nanjing Kinghua Operations Research and Artificial Intelligence, Industrial Technology Research Institute Co., Ltd., Nanjing 210035, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaoyan","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Mathematical Science & Institute of Mathematics, Nanjing Normal University, Nanjing 210023, P. R. China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2023,5,27]]},"reference":[{"issue":"3","key":"S0217595923400122BIB002","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"Chvatal V","year":"1979","journal-title":"Mathematics of Operations Research"},{"key":"S0217595923400122BIB003","doi-asserted-by":"crossref","first-page":"624","DOI":"10.1145\/2591796.2591884","volume-title":"Proc. Forty-Sixth Annual ACM Symp. Theory of Computing","author":"Dinur I","year":"2014"},{"key":"S0217595923400122BIB004","first-page":"69","volume-title":"Combinatorial Structures and Their Applications","author":"Edmonds J","year":"1970"},{"issue":"2","key":"S0217595923400122BIB005","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/S0166-218X(02)00458-4","volume":"131","author":"Fleischer L","year":"2003","journal-title":"Discrete Applied Mathematics"},{"key":"S0217595923400122BIB006","first-page":"755","volume-title":"th Annual IEEE Symp. Foundations of Computer Science","author":"Goel G","year":"2009"},{"issue":"2","key":"S0217595923400122BIB007","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"Gr\u00f6tschel M","year":"1981","journal-title":"Combinatorica"},{"key":"S0217595923400122BIB008","volume-title":"Geometric Algorithms and Combinatorial Optimization","volume":"2","author":"Gr\u00f6tschel M","year":"2012"},{"issue":"4","key":"S0217595923400122BIB009","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"Iwata S","year":"2001","journal-title":"Journal of the ACM"},{"key":"S0217595923400122BIB010","first-page":"671","volume-title":"th Annual IEEE Symp. Foundations of Computer Science","author":"Iwata S","year":"2009"},{"issue":"1","key":"S0217595923400122BIB011","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/s10107-016-1038-y","volume":"162","author":"Jegelka S","year":"2017","journal-title":"Mathematical Programming"},{"issue":"3","key":"S0217595923400122BIB012","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"Johnson DS","year":"1974","journal-title":"Journal of Computer and System Sciences"},{"key":"S0217595923400122BIB013","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/978-3-642-20877-5_14","volume-title":"Int. Conf. Theory and Applications of Models of Computation","author":"Kamiyama N","year":"2011"},{"key":"S0217595923400122BIB014","first-page":"90","volume-title":"Int. Workshop Approximation and Online Algorithms","author":"Kamiyama N","year":"2017"},{"key":"S0217595923400122BIB015","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"Karp RM","year":"1972"},{"issue":"1","key":"S0217595923400122BIB016","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s00453-012-9629-3","volume":"66","author":"Koufogiannakis C","year":"2013","journal-title":"Algorithmica"},{"issue":"4","key":"S0217595923400122BIB017","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"Lov\u00e1sz L","year":"1975","journal-title":"Discrete Mathematics"},{"key":"S0217595923400122BIB018","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/978-3-642-68874-4_10","volume-title":"Mathematical Programming The State of the Art","author":"Lov\u00e1sz L","year":"1983"},{"issue":"3","key":"S0217595923400122BIB019","doi-asserted-by":"crossref","first-page":"771","DOI":"10.1007\/s00453-016-0174-3","volume":"78","author":"McCormick ST","year":"2017","journal-title":"Algorithmica"},{"issue":"1","key":"S0217595923400122BIB020","first-page":"313","volume":"83","author":"Murota K","year":"1998","journal-title":"Mathematical Programming"},{"issue":"2","key":"S0217595923400122BIB021","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"Schrijver A","year":"2000","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"S0217595923400122BIB022","doi-asserted-by":"crossref","first-page":"126442","DOI":"10.1016\/j.amc.2021.126442","volume":"410","author":"Shi M","year":"2021","journal-title":"Applied Mathematics and Computation"},{"issue":"6","key":"S0217595923400122BIB023","doi-asserted-by":"crossref","first-page":"1715","DOI":"10.1137\/100783352","volume":"40","author":"Svitkina Z","year":"2011","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"S0217595923400122BIB024","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"Wolsey LA","year":"1982","journal-title":"Combinatorica"}],"container-title":["Asia-Pacific Journal of Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0217595923400122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,4]],"date-time":"2023-10-04T08:01:14Z","timestamp":1696406474000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0217595923400122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,27]]},"references-count":23,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2023,10]]}},"alternative-id":["10.1142\/S0217595923400122"],"URL":"https:\/\/doi.org\/10.1142\/s0217595923400122","relation":{},"ISSN":["0217-5959","1793-7019"],"issn-type":[{"type":"print","value":"0217-5959"},{"type":"electronic","value":"1793-7019"}],"subject":[],"published":{"date-parts":[[2023,5,27]]},"article-number":"2340012"}}