{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:09Z","timestamp":1740122409786,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T00:00:00Z","timestamp":1663804800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T00:00:00Z","timestamp":1663804800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100010909","name":"Young Scientists Fund","doi-asserted-by":"publisher","award":["12001335"],"award-info":[{"award-number":["12001335"]}],"id":[{"id":"10.13039\/501100010909","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2019PA004","ZR2020MA029"],"award-info":[{"award-number":["ZR2019PA004","ZR2020MA029"]}],"id":[{"id":"10.13039\/501100007129","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2021MA100"],"award-info":[{"award-number":["ZR2021MA100"]}],"id":[{"id":"10.13039\/501100007129","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":[[2022,12]]},"DOI":"10.1007\/s10878-022-00914-6","type":"journal-article","created":{"date-parts":[[2022,9,22]],"date-time":"2022-09-22T07:03:00Z","timestamp":1663830180000},"page":"3549-3574","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast algorithms for supermodular and non-supermodular minimization via bi-criteria strategy"],"prefix":"10.1007","volume":"44","author":[{"given":"Xiaojuan","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Qian","family":"Liu","sequence":"additional","affiliation":[]},{"given":"Min","family":"Li","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5692-6281","authenticated-orcid":false,"given":"Yang","family":"Zhou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,22]]},"reference":[{"issue":"2","key":"914_CR1","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1137\/12086755X","volume":"43","author":"C Boutsidis","year":"2014","unstructured":"Boutsidis C, Drineas P, Magdon-Ismail M (2014) Near-optimal column-based matrix reconstruction. SIAM J Comput 43(2):687\u2013717","journal-title":"SIAM J Comput"},{"key":"914_CR2","unstructured":"Dhillon I, Jain P, Rao N (2016) Structured sparse regression via greedy hard thresholding. In: Advances in neural information processing systems, vol 29"},{"key":"914_CR3","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1080\/01969727308546046","volume":"3","author":"J Dunn","year":"1973","unstructured":"Dunn J (1973) A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters. Cybernetics 3:32\u201357","journal-title":"Cybernetics"},{"issue":"1","key":"914_CR4","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"ML Fisher","year":"1978","unstructured":"Fisher ML, Nemhauser GL, Wolsey LA (1978) An analysis of approximations for maximizing submodular set functions\u2014I. Math Program 14(1):265\u2013294","journal-title":"Math Program"},{"issue":"3","key":"914_CR5","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/BF01436075","volume":"7","author":"G Golub","year":"1965","unstructured":"Golub G (1965) Numerical methods for solving linear least squares problems. Numer Math 7(3):206\u2013216","journal-title":"Numer Math"},{"key":"914_CR6","first-page":"15","volume-title":"Adaptive sampling for k-means clustering","author":"R Kannan","year":"2009","unstructured":"Kannan R, Aggarwal A, Deshpande A (2009) Adaptive sampling for k-means clustering, vol 5678. Springer, Berlin, pp 15\u201325"},{"key":"914_CR7","unstructured":"Kempe D, Das A (2011) Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In: Proceedings of the 28th international conference on international conference on machine learning, pp 1057\u20131064"},{"key":"914_CR8","unstructured":"Krause A, Tschiatschek S, Bian A, Buhmann J (2017) Guarantees for greedy maximization of non-submodular functions with applications. In: Proceedings of the 34th international conference on machine learning, pp 498\u2013507"},{"key":"914_CR9","unstructured":"Nowak R, Rogers TT, Rao N, Cox C (2013) Sparse overlapping sets lasso for multitask learning and its application to FMRI analysis. In: Advances in neural information processing systems, vol 26"},{"issue":"1","key":"914_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/opre.2020.1992","volume":"69","author":"J Qi","year":"2021","unstructured":"Qi J, Chen X, Long DZ (2021) Preservation of supermodularity in parametric optimization: necessary and sufficient conditions on constraint structures. Oper Res 69(1):1\u201312","journal-title":"Oper Res"},{"key":"914_CR11","doi-asserted-by":"crossref","unstructured":"Rademacher L, Deshpande A (2010) Efficient volume sampling for row\/column subset selection. In: 2010 IEEE 51st annual symposium on foundations of computer science. IEEE, pp 329\u2013338","DOI":"10.1109\/FOCS.2010.38"},{"key":"914_CR12","unstructured":"Shashua A, Zass R (2005) A unifying approach to hard and probabilistic clustering. In: Tenth IEEE international conference on computer vision (ICCV\u201905) vol 1. IEEE, pp 294\u2013301"},{"key":"914_CR13","doi-asserted-by":"crossref","unstructured":"Singer Y, Balkanski E (2018) The adaptive complexity of maximizing a submodular function. In: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pp 1138\u20131151","DOI":"10.1145\/3188745.3188752"},{"key":"914_CR14","doi-asserted-by":"crossref","unstructured":"Singer Y, Balkanski E, Rubinstein A (2019) An exponential speedup in parallel running time for submodular maximization without loss in approximation. In: Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms. SIAM, pp 283\u2013302","DOI":"10.1137\/1.9781611975482.19"},{"key":"914_CR15","unstructured":"Sviridenko M, Liberty E (2017) Greedy minimization of weakly supermodular set functions. In: Approximation, randomization, and combinatorial optimization. Algorithms and techniques (APPROX\/RANDOM 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"issue":"4","key":"914_CR16","doi-asserted-by":"publisher","first-page":"1197","DOI":"10.1287\/moor.2016.0842","volume":"42","author":"J Ward","year":"2017","unstructured":"Ward J, Sviridenko M, Vondr\u00e1k J (2017) Optimal approximation for submodular and supermodular optimization with bounded curvature. Math Oper Res 42(4):1197\u20131218","journal-title":"Math Oper Res"},{"key":"914_CR17","unstructured":"Woodruff DP, Indyk P, Price E (2011) On the power of adaptivity in sparse recovery. In: 2011 IEEE 52nd annual symposium on foundations of computer science. IEEE, pp 285\u2013294"},{"key":"914_CR18","first-page":"107","volume":"149","author":"Z Yuan","year":"2021","unstructured":"Yuan Z, Liu B, Zhang Q (2021) Two-stage distributionally robust optimization for maritime inventory routing. Comput Chem Eng 149:107\u2013307","journal-title":"Comput Chem Eng"},{"key":"914_CR19","doi-asserted-by":"crossref","unstructured":"Zadimoghaddam M, Fahrbach M, Mirrokni V (2019) Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In: Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms. SIAM, pp. 255\u2013273","DOI":"10.1137\/1.9781611975482.17"},{"issue":"6","key":"914_CR20","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1137\/110839655","volume":"43","author":"R Zenklusen","year":"2014","unstructured":"Zenklusen R, Chekuri C, Vondr\u00e1k J (2014) Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J Comput 43(6):1831\u20131879","journal-title":"SIAM J Comput"},{"issue":"6","key":"914_CR21","doi-asserted-by":"publisher","first-page":"2807","DOI":"10.1137\/090759574","volume":"20","author":"T Zhang","year":"2010","unstructured":"Zhang T, Shalev-Shwartz S, Srebro N (2010) Trading accuracy for sparsity in optimization problems with sparsity constraints. SIAM J Optim 20(6):2807\u20132832","journal-title":"SIAM J Optim"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00914-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00914-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00914-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,29]],"date-time":"2022-10-29T09:40:23Z","timestamp":1667036423000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00914-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,22]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["914"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00914-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2022,9,22]]},"assertion":[{"value":"15 September 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 September 2022","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 have not disclosed any conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}