{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:17:17Z","timestamp":1742915837313,"version":"3.40.3"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030592660"},{"type":"electronic","value":"9783030592677"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-59267-7_6","type":"book-chapter","created":{"date-parts":[[2020,10,11]],"date-time":"2020-10-11T19:02:33Z","timestamp":1602442953000},"page":"60-68","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Primal-Dual Randomized Algorithm for the Online Weighted Set Multi-cover Problem"],"prefix":"10.1007","author":[{"given":"Wenbin","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fufang","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ke","family":"Qi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miao","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maobin","family":"Tang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,10,9]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. In: STOC 2003, pp. 100\u2013105 (2003)","DOI":"10.1145\/780542.780558"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Bansal, N., Buchbinder, N., Naor, J.: A primal-dual randomized algorithm for weighted paging. In: FOCS 2007, pp. 507\u2013517 (2007)","DOI":"10.1109\/FOCS.2007.43"},{"key":"6_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-540-75520-3_24","volume-title":"Algorithms \u2013 ESA 2007","author":"N Buchbinder","year":"2007","unstructured":"Buchbinder, N., Jain, K., Naor, J.S.: Online primal-dual algorithms for maximizing ad-auctions revenue. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol. 4698, pp. 253\u2013264. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-75520-3_24"},{"key":"6_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1007\/11561071_61","volume-title":"Algorithms \u2013 ESA 2005","author":"N Buchbinder","year":"2005","unstructured":"Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing problems. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 689\u2013701. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11561071_61"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Naor, J.: Improved bounds for online routing and packing via a primal-dual approach. In: Proceedings of the 47th Symposium on Foundations of Computer Science (FOCS), pp. 293\u2013304 (2006)","DOI":"10.1109\/FOCS.2006.39"},{"issue":"2\u20133","key":"6_CR6","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"N Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal-dual approach. Found. Trends Theor. Comput. Sci. 3(2\u20133), 93\u2013263 (2009)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"6_CR7","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chvatal","year":"1979","unstructured":"Chvatal, V.: A greedy heuristic for the set covering problem. Math. Oper. Res. 4, 233\u2013235 (1979)","journal-title":"Math. Oper. Res."},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. In: Proceedings of the 28th ACM Symposium on the Theory of Computing, pp. 312\u2013318 (1996)","DOI":"10.1145\/237814.237977"},{"issue":"4","key":"6_CR9","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson, D.S.: Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256\u2013278 (1974)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR11","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"issue":"4","key":"6_CR12","doi-asserted-by":"publisher","first-page":"1237","DOI":"10.1007\/s10878-017-0144-y","volume":"34","author":"A Kuhnle","year":"2017","unstructured":"Kuhnle, A., Li, X., Smith, J.D., Thai, M.T.: Online set multicover algorithms for dynamic D2D communications. J. Comb. Optim. 34(4), 1237\u20131264 (2017). https:\/\/doi.org\/10.1007\/s10878-017-0144-y","journal-title":"J. Comb. Optim."},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Lov$$\\acute{a}$$sz, L.: On the ratio of optimal integral and fractional covers. Discrete Math. 13, 383\u2013390 (1975)","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. In: Proceedings of the 25th ACM Symposium on Theory of Computing, pp. 286\u2013293 (1993)","DOI":"10.1145\/167088.167172"},{"issue":"28","key":"6_CR15","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1137\/S0097539793260763","volume":"109","author":"S Rajagopalan","year":"1998","unstructured":"Rajagopalan, S., Vazirani, V.V.: Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM J. Comput. 109(28), 525\u2013540 (1998)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"6_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1177\/1550147717695561","volume":"13","author":"Z Sun","year":"2017","unstructured":"Sun, Z., Li, L., Li, X., Xing, X., Li, Y.: Optimization coverage conserving protocol with authentication in wireless sensor networks. Int. J. Distrib. Sens. Netw. 13(3), 1\u201316 (2017)","journal-title":"Int. J. Distrib. Sens. Netw."},{"issue":"2","key":"6_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1177\/1550147717693242","volume":"13","author":"Z Sun","year":"2017","unstructured":"Sun, Z., Li, C., Xing, X., Wang, H., Yan, B., Li, X.: K-degree coverage algorithm based on optimization nodes deployment in wireless sensor networks. Int. J. Distrib. Sens. Netw. 13(2), 1\u201316 (2017)","journal-title":"Int. J. Distrib. Sens. Netw."},{"issue":"1\/4","key":"6_CR18","first-page":"173","volume":"33","author":"Z Sun","year":"2016","unstructured":"Sun, Z., Shu, Y., Xing, X., et al.: LPOCS: a novel linear programming optimization coverage scheme in wireless sensor networks. J. Ad Hoc Sens. Wirel. Netw. 33(1\/4), 173\u2013197 (2016)","journal-title":"J. Ad Hoc Sens. Wirel. Netw."},{"issue":"8","key":"6_CR19","first-page":"3621","volume":"10","author":"Z Sun","year":"2016","unstructured":"Sun, Z., Zhang, Y., Xing, X., et al.: EBKCCA: a novel energy balanced $$k$$-coverage control algorithm based on probability model in wireless sensor networks. KSII Trans. Internet Inf. Syst. 10(8), 3621\u20133640 (2016)","journal-title":"KSII Trans. Internet Inf. Syst."},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Sun, Z., Wang, H., Wu, W., Xing, X.: ECAPM: an enhanced coverage algorithm in wireless sensor network based on probability model. Int. J. Distrib. Sens. Netw. 2015Article ID 203502, 11 pages (2015)","DOI":"10.1155\/2015\/203502"},{"key":"6_CR21","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1007\/BF01189992","volume":"11","author":"NE Young","year":"1994","unstructured":"Young, N.E.: The k-server dual and loose competitiveness for paging. Algorithmica 11, 525\u2013541 (1994). Preliminary version appeared in SODA\u201991 titled \u201cOn-Line Caching as Cache Size Varies\u201d","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Models of Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-59267-7_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T18:08:35Z","timestamp":1710353315000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-59267-7_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030592660","9783030592677"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-59267-7_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"9 October 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TAMC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Theory and Applications of Models of Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Changsha","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 October 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 October 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tamc2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/tamc2020.csu.edu.cn\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"83","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"45% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"7","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}