{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:55Z","timestamp":1740122455578,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,3,10]],"date-time":"2017-03-10T00:00:00Z","timestamp":1489104000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11531011","61222201"],"award-info":[{"award-number":["11531011","61222201"]}],"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":[[2017,10]]},"DOI":"10.1007\/s10878-017-0122-4","type":"journal-article","created":{"date-parts":[[2017,3,10]],"date-time":"2017-03-10T07:53:43Z","timestamp":1489132423000},"page":"956-963","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A simple approximation algorithm for minimum weight partial connected set cover"],"prefix":"10.1007","volume":"34","author":[{"given":"Yubai","family":"Zhang","sequence":"first","affiliation":[]},{"given":"Yingli","family":"Ran","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4191-7598","authenticated-orcid":false,"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,3,10]]},"reference":[{"key":"122_CR1","doi-asserted-by":"crossref","unstructured":"Bateni M, Hajiaghayi M, Liaghat V (2013) Improved approximation algorithms for (budgeted) node-weighted steiner problems. In: ICALP, pp 81\u201392","DOI":"10.1007\/978-3-642-39206-1_8"},{"issue":"3","key":"122_CR2","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal V (1979) A greedy heuristic for the set covering problem. Math Oper Res 4(3):233\u2013235","journal-title":"Math Oper Res"},{"key":"122_CR3","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1007\/s10898-012-9871-x","volume":"56","author":"H Du","year":"2013","unstructured":"Du H, Pardalos PM, Wu W, Wu L (2013) Maximum lifetime connected coverage with two active-phase sensors. J Glob Optim 56:559\u2013568","journal-title":"J Glob Optim"},{"key":"122_CR4","doi-asserted-by":"crossref","unstructured":"Edwards K, Griffiths S, Kennedy WS (2013) Partial interval set cover\u2014trade-offs between scalability and optimality. In: Raghavendra P, Raskhodnikova S, Jansen K, Rolim JDP (eds) Approximation, randomization, and combinatorial optimization. algorithms and techniques. Lecture notes in computer science, vol 8096. Springer, Berlin, Heidelberg, pp 102\u2013113","DOI":"10.1007\/978-3-642-40328-6_9"},{"key":"122_CR5","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.tcs.2012.02.035","volume":"438","author":"K Elbassioni","year":"2012","unstructured":"Elbassioni K, Jeli\u0107 S, Matijevi\u0107 D (2012) The relation of connected set cover and group steiner tree. Theor Comput Sci 438:96\u2013101","journal-title":"Theor Comput Sci"},{"key":"122_CR6","doi-asserted-by":"crossref","unstructured":"Elomaa T, Kujala J (2010) Covering analysis of the greedy algorithm for partial cover. In: Elomaa T, Mannila H, Orponen P (eds) Algorithms and applications. Lecture notes in computer science, vol 6060. Springer, Berlin, Heidelberg, pp 102\u2013113","DOI":"10.1007\/978-3-642-12476-1_7"},{"key":"122_CR7","doi-asserted-by":"crossref","unstructured":"Feige U (1998) A threshold of \n                        $$\\ln n$$\n                        \n                            \n                                            \n                                \n                                    ln\n                                    n\n                                \n                            \n                        \n                     for approximating set cover. J ACM 45:634\u2013652","DOI":"10.1145\/285055.285059"},{"key":"122_CR8","volume-title":"Computers and intractability","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability. W.H. Freeman and Company, New York"},{"key":"122_CR9","doi-asserted-by":"crossref","unstructured":"Garg N (2005) Saving an epsilon: a 2-approximation for the \n                        $$k$$\n                        \n                            \n                                            \n                                k\n                            \n                        \n                    -MST problem in graphs. In: STOC, pp 396\u2013402","DOI":"10.1145\/1060590.1060650"},{"issue":"1","key":"122_CR10","doi-asserted-by":"crossref","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":"122_CR11","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D Johnson","year":"1974","unstructured":"Johnson D (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9:256\u2013278","journal-title":"J Comput Syst Sci"},{"key":"122_CR12","unstructured":"Johnson D, Minkoff M, Phillips S (2000) The prize collecting steiner tree problem: theorem and practice. In: SODA, pp 70\u2013769"},{"key":"122_CR13","volume-title":"The computational complexity of machine learning","author":"MJ Kearns","year":"1990","unstructured":"Kearns MJ (1990) The computational complexity of machine learning, vol 21(3). The MIT Press, Cambridge"},{"key":"122_CR14","doi-asserted-by":"crossref","unstructured":"Khandekar R, Kortsarz G, Nutov Z (2012) Approximating fault-tolerant group steiner problem. Theor Comput Sci 416:55\u201364","DOI":"10.1016\/j.tcs.2011.08.021"},{"key":"122_CR15","unstructured":"Khuller S, Purohit M, Sarpatwar KK (2013) Analyzing the optimal neighborhood: algorithms for budgeted and partial connected dominating set problems. In: ACM-SIAM symposium on discrete algorithms, pp 1702\u20131713"},{"issue":"4","key":"122_CR16","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1007\/s00453-009-9317-0","volume":"59","author":"J K\u00f6nemann","year":"2011","unstructured":"K\u00f6nemann J, Parekh O, Segv D (2011) A unified approach to approximating partial covering problems. Algorithmica 59(4):489\u2013509","journal-title":"Algorithmica"},{"key":"122_CR17","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1007\/s10878-014-9782-5","volume":"31","author":"D Liang","year":"2016","unstructured":"Liang D, Zhang Z, Liu X, Wang W, Jiang Y (2016) Approximation algorithms for minimum weight partial connected set cover problem. J Comb Optim 31:696\u2013712","journal-title":"J Comb Optim"},{"key":"122_CR18","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/0012-365X(75)90058-8","volume":"13","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz L (1975) On the ratio of optimal integral and fractional covers. Discrete Math 13:383\u2013390","journal-title":"Discrete Math"},{"issue":"4","key":"122_CR19","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/j.ipl.2008.05.007","volume":"108","author":"P Miettnen","year":"2008","unstructured":"Miettnen P (2008) On the positive\u2013negative partial set cover problem. Inf Process Lett 108(4):219\u2013221","journal-title":"Inf Process Lett"},{"key":"122_CR20","doi-asserted-by":"crossref","unstructured":"Moss A, Rabani Y (2007) Approximation algorithms for constrained node weighted steiner tree problems. SIAM J Comput 37(2):460\u2013481","DOI":"10.1137\/S0097539702420474"},{"key":"122_CR21","doi-asserted-by":"crossref","unstructured":"Ran Y, Zhang Z, Ko KI, Liang J (2016) An approximation algorithm for maximum weight budgeted connected set cover. J Comb Optim 31:1505\u20131517","DOI":"10.1007\/s10878-015-9838-1"},{"key":"122_CR22","first-page":"243","volume":"4104","author":"T Shuai","year":"2006","unstructured":"Shuai T, Hu X (2006) Connected set cover problem and its application. Algorithm Appl Manag 4104:243\u2013254","journal-title":"Algorithm Appl Manag"},{"key":"122_CR23","doi-asserted-by":"crossref","unstructured":"Slav\u00edk P(1997) Improved performance of the greedy algorithm for partial cover. Inf Process Lett 64:251\u2013254","DOI":"10.1016\/S0020-0190(97)00182-8"},{"key":"122_CR24","doi-asserted-by":"crossref","unstructured":"Wu L, Du H, Wu W, Li D, Lv J, Lee W (2013) Approximations for minimum connected sensor cover. In: Proceedings IEEE INFOCOM","DOI":"10.1109\/INFCOM.2013.6566910"},{"issue":"2","key":"122_CR25","first-page":"137","volume":"39","author":"B Yehuda","year":"2001","unstructured":"Yehuda B (2001) Using homogeneous weights for approximating the partial cover problem. Computer science department, Journal of Algorithm 39(2):137\u2013144","journal-title":"Computer science department, Journal of Algorithm"},{"key":"122_CR26","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1016\/j.tcs.2008.11.005","volume":"410","author":"Z Zhang","year":"2009","unstructured":"Zhang Z, Gao X, Wu W (2009) Algorithms for connected set cover problem and fault-tolerant connected set cover problem. Theor Comput Sci 410:812\u2013817","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-017-0122-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0122-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-017-0122-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,9,21]],"date-time":"2017-09-21T08:38:49Z","timestamp":1505983129000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-017-0122-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,10]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["122"],"URL":"https:\/\/doi.org\/10.1007\/s10878-017-0122-4","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2017,3,10]]}}}