{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,6]],"date-time":"2026-01-06T13:54:51Z","timestamp":1767707691251,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871081","11771386"],"award-info":[{"award-number":["11871081","11771386"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11728104"],"award-info":[{"award-number":["11728104"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["06446"],"award-info":[{"award-number":["06446"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11871280"],"award-info":[{"award-number":["11871280"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013088","name":"Qinglan Project of Jiangsu Province of China","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100013088","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004731","name":"Natural Science Foundation of Zhejiang Province","doi-asserted-by":"publisher","award":["LY20A010013"],"award-info":[{"award-number":["LY20A010013"]}],"id":[{"id":"10.13039\/501100004731","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,11]]},"DOI":"10.1007\/s10878-021-00753-x","type":"journal-article","created":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T21:02:51Z","timestamp":1626901371000},"page":"2626-2641","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Approximation algorithms for stochastic set cover and single sink rent-or-buy with submodular penalty"],"prefix":"10.1007","volume":"44","author":[{"given":"Jian","family":"Sun","sequence":"first","affiliation":[]},{"given":"Haiyun","family":"Sheng","sequence":"additional","affiliation":[]},{"given":"Yuefang","family":"Sun","sequence":"additional","affiliation":[]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3085-2701","authenticated-orcid":false,"given":"Xiaoyan","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,7,21]]},"reference":[{"issue":"3","key":"753_CR1","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00493-003-0025-0","volume":"23","author":"A Arora","year":"2003","unstructured":"Arora A, Sudan M (2003) Improved low degree testing and applications. Combinatorica 23(3):365\u2013426","journal-title":"Combinatorica"},{"key":"753_CR2","doi-asserted-by":"crossref","unstructured":"Balkanski E, Singer Y (2020) A lower bound for parallel submodular minimization. In: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing (STOC), pp 130\u2013139","DOI":"10.1145\/3357713.3384287"},{"key":"753_CR3","doi-asserted-by":"crossref","unstructured":"Bellare M, Goldwass S, Lund C, Russell A (1994) Efficient probabilistically checkable proofs and applications to approximations. In: Proceedings of the 26th annual ACM symposium on theory of computing (STOC), pp 23\u201325","DOI":"10.1145\/195058.195467"},{"key":"753_CR4","doi-asserted-by":"crossref","unstructured":"Byrka J, Grandon F (2010) An improved LP-based approximation for Steiner tree. In: Proceedings of the 42nd ACM symposium on theory of computing (STOC), pp 5\u20138","DOI":"10.1145\/1806689.1806769"},{"issue":"2","key":"753_CR5","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0166-218X(02)00458-4","volume":"131","author":"L Fleischer","year":"2003","unstructured":"Fleischer L, Iwata S (2003) A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Appl Math 131(2):311\u2013322","journal-title":"Discrete Appl Math"},{"issue":"1","key":"753_CR6","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jalgor.2004.04.002","volume":"53","author":"R Gandhi","year":"2004","unstructured":"Gandhi R, Khuller S, Srinivasan A (2004) Approximation algorithms for partial covering problems. J Algorithms 53(1):55\u201384","journal-title":"J Algorithms"},{"key":"753_CR7","doi-asserted-by":"crossref","unstructured":"Gupta A, Kleinberg J, Kumar A, Rastogi R, Yener B (2001) Provisioning a virtual private network: a network design problem for multicommodity flow. In: Proceedings of the 33rd annual ACM symposium on theory of computing (STOC), pp 389\u2013398","DOI":"10.1145\/380752.380830"},{"issue":"3","key":"753_CR8","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"D-S Hochbaum","year":"1982","unstructured":"Hochbaum D-S (1982) Approximation algorithm for set covering and vertex cover problems. SIAM J Comput 11(3):555\u2013556","journal-title":"SIAM J Comput"},{"issue":"3","key":"753_CR9","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D-S Johnson","year":"1974","unstructured":"Johnson D-S (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9(3):256\u2013278","journal-title":"J Comput Syst Sci"},{"key":"753_CR10","unstructured":"Karger D-R, Minkoff M (2000) Building Steiner trees with incomplete global knowledge. In: Proceedings of the 41st annual symposium on foundations of computer science (FOCS), pp 613\u2013623"},{"key":"753_CR11","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"R-M Karp","year":"1972","unstructured":"Karp R-M (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (eds) Complexity of computer computations. The IBM Research Symposia Series. Springer, Boston, pp 85\u2013103"},{"issue":"4","key":"753_CR12","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0020-0190(02)00271-5","volume":"84","author":"S Khuller","year":"2002","unstructured":"Khuller S, Zhu A (2002) The general Steiner tree-star problem. Inf Process Lett 84(4):215\u2013220","journal-title":"Inf Process Lett"},{"key":"753_CR13","volume-title":"The computational complexity of machine learning","author":"M-J Kearns","year":"1990","unstructured":"Kearns M-J (1990) The computational complexity of machine learning. The MIT Press, Cambridge"},{"issue":"3","key":"753_CR14","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/(SICI)1097-0037(199610)28:3<167::AID-NET5>3.0.CO;2-L","volume":"28","author":"T-U Kim","year":"1996","unstructured":"Kim T-U, Lowe T-J, Tamir A, Ward J-E (1996) On the location of a tree-shaped facility. Networks 28(3):167\u2013175","journal-title":"Networks"},{"issue":"4","key":"753_CR15","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/s00453-009-9317-0","volume":"59","author":"J K\u00f6nemann","year":"2011","unstructured":"K\u00f6nemann J, Parekh O, Segev D (2011) A unified approach to approximating partial covering problems. Algorithmica 59(4):489\u2013509","journal-title":"Algorithmica"},{"key":"753_CR16","unstructured":"Labb\u00e9 M, Laporte G, Martin I-R, Gonz\u00e1lez J-J-S (2001) The median cycle problem. Technical Report 2001\/12, Department of Operations Research and Multicriteria Decision Aid at Universit\u00e9 Libre de Bruxelles"},{"issue":"3","key":"753_CR17","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1287\/ijoc.8.3.194","volume":"8","author":"Y Lee","year":"1996","unstructured":"Lee Y, Chiu S-Y, Ryan J (1996) A branch and cut algorithm for a Steiner tree-star problem. Inf J Comput 8(3):194\u2013201","journal-title":"Inf J Comput"},{"issue":"1","key":"753_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s40305-015-0116-9","volume":"4","author":"J Li","year":"2016","unstructured":"Li J, Liu Y (2016) Approximation algorithms for stochastic combinatorial optimization problems. J Oper Res Soc China 4(1):1\u201347","journal-title":"J Oper Res Soc China"},{"key":"753_CR19","unstructured":"Parthasarathy S (2018) Adaptive greedy algorithms for stochastic set cover problems. arXiv:1803.07639"},{"issue":"1","key":"753_CR20","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/s10107-005-0673-5","volume":"108","author":"R Ravic","year":"2006","unstructured":"Ravic R, Sinhac A (2006) Hedging uncertainty: approximation algorithms for stochastic optimization problems. Math Programm 108(1):97\u2013114","journal-title":"Math Programm"},{"key":"753_CR21","doi-asserted-by":"crossref","unstructured":"Raz R, Safra S (1997) A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the 29th annual ACM symposium on the theory of computing (STOC), pp 4\u20136","DOI":"10.1145\/258533.258641"},{"issue":"5","key":"753_CR22","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0020-0190(97)00182-8","volume":"64","author":"P Slavik","year":"1997","unstructured":"Slavik P (1997) Improved performance of greedy algorithm for partial over. Inf Process Lett 64(5):251\u2013254","journal-title":"Inf Process Lett"},{"issue":"4","key":"753_CR23","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00453-004-1112-3","volume":"40","author":"C Swamy","year":"2004","unstructured":"Swamy C, Kumar A (2004) Primal-dual algorithms for connected facility location problems. Algorithmica 40(4):245\u2013269","journal-title":"Algorithmica"},{"key":"753_CR24","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.tcs.2020.11.007","volume":"850","author":"S Tang","year":"2021","unstructured":"Tang S (2021) Beyond pointwise submodularity: non-monotone adaptive submodular maximization in linear time. Theor Comput Sci 850:249\u2013261","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00753-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00753-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00753-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:19:42Z","timestamp":1665778782000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00753-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["753"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00753-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"1 May 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 July 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}