{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T00:50:56Z","timestamp":1768524656768,"version":"3.49.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,8,17]],"date-time":"2016-08-17T00:00:00Z","timestamp":1471392000000},"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"],"award-info":[{"award-number":["11531011"]}],"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,7]]},"DOI":"10.1007\/s10878-016-0066-0","type":"journal-article","created":{"date-parts":[[2016,8,17]],"date-time":"2016-08-17T07:17:25Z","timestamp":1471418245000},"page":"302-313","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Local ratio method on partial set multi-cover"],"prefix":"10.1007","volume":"34","author":[{"given":"Yingli","family":"Ran","sequence":"first","affiliation":[]},{"given":"Yishuo","family":"Shi","sequence":"additional","affiliation":[]},{"given":"Zhao","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,8,17]]},"reference":[{"key":"66_CR1","first-page":"27","volume":"25","author":"R Bar-Yehuda","year":"1985","unstructured":"Bar-Yehuda R, Even S (1985) A local-ratio theorem for approximating the weighted vertex cover problem. Ann Discret Math 25:27\u201346","journal-title":"Ann Discret Math"},{"key":"66_CR2","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jagm.2000.1150","volume":"39","author":"R Bar-Yehuda","year":"2001","unstructured":"Bar-Yehuda R (2001) Using homogeneous weights for approximating the partial cover problem. J Algorithms 39:137\u2013144","journal-title":"J Algorithms"},{"key":"66_CR3","unstructured":"Bshouty NH, Burroughs L (1998) Massaging a linear programming solution to give a 2-approximation for a generalization of the vertex cover problem. In: The proceedings of the 15th annual symposium on the theoretical aspects of computer science, pp 298\u2013308"},{"key":"66_CR4","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:233\u2013235","journal-title":"Math Oper Res"},{"key":"66_CR5","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/s10878-012-9530-7","volume":"27","author":"TN Dinh","year":"2014","unstructured":"Dinh TN, Shen Y, Nguyen DT, Thai MT (2014) On the approximability of positive influence dominating set in social networks. J Comb Optim 27:487\u2013503","journal-title":"J Comb Optim"},{"key":"66_CR6","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1287\/moor.7.4.515","volume":"7","author":"G Dobson","year":"1982","unstructured":"Dobson G (1982) Worst-case analysis of greedy heuristics for integer programming with nonnegative data. Math Oper Res 7:515\u2013531","journal-title":"Math Oper Res"},{"key":"66_CR7","unstructured":"Feige U (1996) A threshold of ln $$n$$ n for approximating set cover. In: Proceedings of the 28th ACM symposium on the theory of computing, pp 312\u2013318"},{"key":"66_CR8","doi-asserted-by":"crossref","first-page":"584","DOI":"10.1137\/0603059","volume":"3","author":"ML Fisher","year":"1982","unstructured":"Fisher ML, Wolsey LA (1982) On the greedy heuristic for continuous covering and packing problems. SIAM J Algeb Discret Methods 3:584\u2013591","journal-title":"SIAM J Algeb Discret Methods"},{"issue":"1","key":"66_CR9","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":"66_CR10","doi-asserted-by":"crossref","unstructured":"Halperin E, Srinivasan A (2002) Improved approximation algorithms for the partial vertex cover problem. In: 5th international workshop on approximation algorithms for combinatorial optimization problems, LNCS, vol 2462, pp 161\u2013174","DOI":"10.1007\/3-540-45753-4_15"},{"key":"66_CR11","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1137\/0211045","volume":"11","author":"DS Hochbaum","year":"1982","unstructured":"Hochbaum DS (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM J Comput 11:555\u2013556","journal-title":"SIAM J Comput"},{"key":"66_CR12","doi-asserted-by":"crossref","unstructured":"Hochbaum DS (1998) The $$t$$ t -vertex cover problem: extending the half integrality framework with budget constraints, In: Proceedings of the first international workshop on approximation algorithms for combinatorial optimization problems, pp 111\u2013122","DOI":"10.1007\/BFb0053968"},{"key":"66_CR13","doi-asserted-by":"crossref","unstructured":"Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9:256\u2013278","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"66_CR14","doi-asserted-by":"crossref","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum Press, New York, pp 85\u2013103","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"66_CR15","unstructured":"Kearns MJ (1990) The computational complexity of machine learning. MIT Press, Cambridge"},{"key":"66_CR16","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1016\/S0166-218X(02)00598-X","volume":"129","author":"SG Kolliopoulos","year":"2003","unstructured":"Kolliopoulos SG (2003) Approximating covering integer programs with multiplicity constraints. Discret Appl Math 129:461\u2013473","journal-title":"Discret Appl Math"},{"key":"66_CR17","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1016\/j.jcss.2005.05.002","volume":"71","author":"SG Kolliopoulos","year":"2005","unstructured":"Kolliopoulos SG, Young Neal E (2005) Approximation algorithms for covering\/packing integer programs. J Comput Syst Sci 71:495\u2013505","journal-title":"J Comput Syst Sci"},{"key":"66_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. Discret Math 13:383\u2013390","journal-title":"Discret Math"},{"key":"66_CR19","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1007\/s10878-014-9793-2","volume":"31","author":"ME Ouali","year":"2016","unstructured":"Ouali ME, Fohlin H, Srivastav A (2016) An approximation algorithm for the partial vertex cover problem in hypergraphs. J Comb Optim 31:846\u2013864","journal-title":"J Comb Optim"},{"key":"66_CR20","doi-asserted-by":"crossref","unstructured":"Rajagopalan S, Vazirani VV (1993) Primal-dual RNC approximation algorithms for (multi)-set (multi)-cover and covering integer programs. In: Proceedings of the 34th annual IEEE symposium on foundations of computer science. Palo Alto, CA, pp 322\u2013331","DOI":"10.1109\/SFCS.1993.366855"},{"key":"66_CR21","doi-asserted-by":"publisher","unstructured":"Ran YL, Zhang Z, Du HW, Zhu YQ (2016) Approximation algorithm for partial positive influence problem in social network. J Comb Optim. doi: 10.1007\/s10878-016-0005-0","DOI":"10.1007\/s10878-016-0005-0"},{"key":"66_CR22","doi-asserted-by":"crossref","unstructured":"Rawitz D, Shahar SH (2011) Partial multicovering and the d-consecutive ones property. Discret Optim 4:555\u2013567","DOI":"10.1016\/j.disopt.2011.05.004"},{"issue":"5","key":"66_CR23","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0020-0190(97)00182-8","volume":"64","author":"P Slav\u00edk","year":"1997","unstructured":"Slav\u00edk P (1997) Improved performance of the greedy algorithm for partial cover. Inf Process Lett 64(5):251\u2013254","journal-title":"Inf Process Lett"},{"key":"66_CR24","unstructured":"Srinivasan A (1996) An extension of the Lov\u00e1sz local lemma and its applications to integer programming. In: Proceedings of the seventh ACM-SIAM symposium on discrete algorithms, pp 6\u201315"},{"key":"66_CR25","doi-asserted-by":"crossref","first-page":"648","DOI":"10.1137\/S0097539796314240","volume":"29","author":"A Srinivasan","year":"1999","unstructured":"Srinivasan A (1999) Improved approximations guarantees for packing and covering integer programs. SIAM J Comput 29:648\u2013670 (preliminary version in Proc. STOC 95)","journal-title":"SIAM J Comput"},{"key":"66_CR26","doi-asserted-by":"crossref","first-page":"2051","DOI":"10.1137\/S0097539798335596","volume":"30","author":"A Srinivasan","year":"2001","unstructured":"Srinivasan A, Teo C-P (2001) A constant-factor approximation algorithm for packet routing and balancing local versus global criteria. SIAM J Comput 30:2051\u20132068 (preliminary version in Proc. STOC 97)","journal-title":"SIAM J Comput"},{"key":"66_CR27","volume-title":"Approximation algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani VV (2001) Approximation algorithms. Springer, Berlin"},{"key":"66_CR28","doi-asserted-by":"crossref","unstructured":"Wang F, Camacho E, Xu K (2009) Positive influence dominating set in online social networks. COCOA, LNCS, vol 5573, pp 313\u2013321","DOI":"10.1007\/978-3-642-02026-1_29"},{"key":"66_CR29","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.tcs.2009.10.001","volume":"412","author":"F Wang","year":"2011","unstructured":"Wang F, Du H, Camacho E, Xu K, Lee W, Shi Y, Shan S (2011) On positive influence dominating sets in social networks. Theor Comput Sci 412:265\u2013269","journal-title":"Theor Comput Sci"},{"key":"66_CR30","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s13278-011-0033-9","volume":"2","author":"W Zhang","year":"2011","unstructured":"Zhang W, Wu W, Wang F, Xu K (2011) Positive influence dominating sets in power-law graphs. Soc Netw Anal Min 2:31\u201337","journal-title":"Soc Netw Anal Min"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-016-0066-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0066-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0066-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-016-0066-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,12]],"date-time":"2019-09-12T12:49:43Z","timestamp":1568292583000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-016-0066-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,17]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["66"],"URL":"https:\/\/doi.org\/10.1007\/s10878-016-0066-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,17]]}}}