{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:21:00Z","timestamp":1740122460114,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,11,5]],"date-time":"2024-11-05T00:00:00Z","timestamp":1730764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,11,5]],"date-time":"2024-11-05T00:00:00Z","timestamp":1730764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11991022","12071459"],"award-info":[{"award-number":["11991022","12071459"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s10878-024-01224-9","type":"journal-article","created":{"date-parts":[[2024,11,5]],"date-time":"2024-11-05T15:53:40Z","timestamp":1730822020000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Non-submodular maximization with a decomposable objective function"],"prefix":"10.1007","volume":"48","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1076-0869","authenticated-orcid":false,"given":"Cheng","family":"Lu","sequence":"first","affiliation":[]},{"given":"Wenguo","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,11,5]]},"reference":[{"key":"1224_CR1","unstructured":"Bai W, Bilmes JA (2018) Greed is still good: maximizing monotone suBmodular + suPermodular (BP) functions. In: Proceedings of the 35th international conference on machine learning (ICML), vol\u00a080, pp 304\u2013313. PMLR"},{"key":"1224_CR2","unstructured":"Bai W, Iyer R, Wei K, Bilmes J (2016) Algorithms for optimizing the ratio of submodular functions. In: Proceedings of the 33rd international conference on machine learning (ICML), vol\u00a048, pp 2751\u20132759. PMLR"},{"key":"1224_CR3","unstructured":"Bian AA, Buhmann JM, Krause A, Tschiatschek S (2017) Guarantees for greedy maximization of non-submodular functions with applications. In: Proceedings of the 34th international conference on machine learning (ICML), vol\u00a070, pp 498\u2013507. PMLR"},{"key":"1224_CR4","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/j.dam.2015.01.026","volume":"186","author":"KM Byrnes","year":"2015","unstructured":"Byrnes KM (2015) A tight analysis of the submodular-supermodular procedure. Discret Appl Math 186:275\u2013282","journal-title":"Discret Appl Math"},{"issue":"3","key":"1224_CR5","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(84)90003-9","volume":"7","author":"M Conforti","year":"1984","unstructured":"Conforti M, Cornu\u00e9jols G (1984) Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discret Appl Math 7(3):251\u2013274","journal-title":"Discret Appl Math"},{"key":"1224_CR6","unstructured":"Das A, Kempe D (2011) Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Proceedings of the 28th international conference on machine learning (ICML), pp 1057\u20131064. PMLR"},{"key":"1224_CR7","unstructured":"El\u00a0Halabi M, Jegelka S (2020) Optimal approximation for unconstrained non-submodular minimization. In: Proceedings of the 37th international conference on machine learning (ICML), vol 119, pp 3961\u20133972. PMLR"},{"issue":"3","key":"1224_CR8","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s00453-020-00757-9","volume":"83","author":"M Feldman","year":"2021","unstructured":"Feldman M (2021) Guess free maximization of submodular and linear sums. Algorithmica 83(3):853\u2013878","journal-title":"Algorithmica"},{"key":"1224_CR9","unstructured":"Harshaw C, Feldman M, Ward J, Karbasi A (2019) Submodular maximization beyond non-negativity: guarantees, fast algorithms, and applications. In: Proceedings of the 36th international conference on machine learning (ICML), vol\u00a097, pp 2634\u20132643. PMLR"},{"key":"1224_CR10","unstructured":"Iyer R, Bilmes J (2012) Algorithms for approximate minimization of the difference between submodular functions, with applications. In: Proceedings of the twenty-eighth conference on uncertainty in artificial intelligence (UAI), pp 407\u2013417. AUAI Press"},{"issue":"10","key":"1224_CR11","doi-asserted-by":"publisher","first-page":"1756","DOI":"10.14778\/3467861.3467866","volume":"14","author":"T Jin","year":"2021","unstructured":"Jin T, Yang Y, Yang R, Shi J, Huang K, Xiao X (2021) Unconstrained submodular maximization with modular costs: tight approximation and application to profit maximization. Proc VLDB Endow 14(10):1756\u20131768","journal-title":"Proc VLDB Endow"},{"key":"1224_CR12","unstructured":"Kazemi E, Minaee S, Feldman M, Karbasi A (2021) Regularized submodular maximization at scale. In: Proceedings of the 38th international conference on machine learning (ICML), vol 139, pp 5356\u20135366. PMLR"},{"issue":"2","key":"1224_CR13","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/j.geb.2005.02.006","volume":"55","author":"B Lehmann","year":"2006","unstructured":"Lehmann B, Lehmann D, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econom Behav 55(2):270\u2013296","journal-title":"Games Econom Behav"},{"key":"1224_CR14","unstructured":"Narasimhan M, Bilmes J (2005) A submodular-supermodular procedure with applications to discriminative structure learning. In: Proceedings of the twenty-first conference on uncertainty in artificial intelligence (UAI), pp 404\u2013412. Morgan Kaufmann Publishers"},{"key":"1224_CR15","doi-asserted-by":"crossref","unstructured":"Nikolakaki SM, Ene A, Terzi E (2021) An efficient framework for balancing submodularity and cost. In: Proceedings of the 27th ACM SIGKDD international conference on knowledge discovery and data mining (KDD), pp 1256\u20131266. AC","DOI":"10.1145\/3447548.3467367"},{"key":"1224_CR16","unstructured":"Perrault P, Healey J, Wen Z, Valko M (2021) On the approximation relationship between optimizing ratio of submodular (RS) and difference of submodular (DS) functions. arXiv:2101.01631"},{"key":"1224_CR17","doi-asserted-by":"crossref","unstructured":"Qian C, Shi J-C, Yu Y, Tang K, Zhou Z-H (2017) Optimizing ratio of monotone set functions. In: Proceedings of the twenty-sixth international joint conference on artificial intelligence (IJCAI), pp 2606\u20132612","DOI":"10.24963\/ijcai.2017\/363"},{"issue":"4","key":"1224_CR18","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1287\/moor.2016.0842","volume":"42","author":"M Sviridenko","year":"2017","unstructured":"Sviridenko M, Vondr\u00e1k J, Ward J (2017) Optimal approximation for submodular and supermodular optimization with bounded curvature. Math Oper Res 42(4):1197\u20131218","journal-title":"Math Oper Res"},{"issue":"3","key":"1224_CR19","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/s40305-019-00244-1","volume":"7","author":"Y-J Wang","year":"2019","unstructured":"Wang Y-J, Da-Chuan X, Jiang Y-J, Zhang D-M (2019) Minimizing ratio of monotone non-submodular functions. J Oper Res Soc China 7(3):449\u2013459","journal-title":"J Oper Res Soc China"},{"key":"1224_CR20","unstructured":"Yang F, He K, Yang L, Du H, Yang J, Yang B, Sun L (2021) Learning interpretable decision rule sets: a submodular optimization approach. In: Proceedings of the 35th international conference on neural information processing systems (NeurIPS), vol\u00a034, pp 27890\u201327902. Curran Associates, Inc"},{"key":"1224_CR21","unstructured":"Yuille AL, Rangarajan A (2001) The concave-convex procedure (CCCP). In: Proceedings of the 14th international conference on neural information processing systems: natural and synthetic (NIPS), vol\u00a014, pp 1033\u20131040. MIT Press"},{"issue":"4","key":"1224_CR22","doi-asserted-by":"publisher","first-page":"915","DOI":"10.1162\/08997660360581958","volume":"15","author":"AL Yuille","year":"2003","unstructured":"Yuille AL, Rangarajan A (2003) The concave-convex procedure. Neural Comput 15(4):915\u2013936","journal-title":"Neural Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01224-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01224-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01224-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,19]],"date-time":"2024-11-19T21:24:07Z","timestamp":1732051447000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01224-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,5]]},"references-count":22,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["1224"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01224-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2024,11,5]]},"assertion":[{"value":"17 October 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 November 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"40"}}