{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,11,15]],"date-time":"2023-11-15T01:38:58Z","timestamp":1700012338890},"reference-count":25,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2007,5,2]],"date-time":"2007-05-02T00:00:00Z","timestamp":1178064000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2007,8]]},"abstract":"Abstract<\/jats:title>In this paper, we consider an interesting generalization of the weighted vertex cover problem, called the Facility Terminal Cover (FTC) problem. In the FTC problem, each vertex is associated with a positive weight, each edge is associated with a positive demand, and the objective is to determine a subset of vertices and a capacity for each selected vertex so that the demand of each edge is covered by the capacity of one of its two endpoints and the total weighted capacity of all selected vertices is minimized. The FTC problem is motivated by several key network optimization problems, such as the power assignment problem in ad hoc networks, and could be used as a subroutine to solve such problems. No quality\u2010guaranteed solution is previously known for the FTC problem. In this paper, we present two linear time approximation algorithms for this problem. Our first algorithm achieves deterministically an approximation ratio of 8 by using an interesting rounding technique and a lower\u2010bounding technique. Based on interesting randomization techniques, our second algorithm further improves the approximation ratio to 2e<\/jats:italic>, where e<\/jats:italic> is the natural logarithmic base. The second algorithm can be easily derandomized in quadratic time. Our algorithms are relatively simple and can be easily implemented for networking applications. Experiments show that the two algorithms behave rather similarly, especially in large\u2010size graphs, indicating that the solutions yielded by one or both algorithms are much closer to the optimum. \u00a9 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(1), 118\u2013126 2007<\/jats:p>","DOI":"10.1002\/net.20172","type":"journal-article","created":{"date-parts":[[2007,5,3]],"date-time":"2007-05-03T16:20:52Z","timestamp":1178209252000},"page":"118-126","source":"Crossref","is-referenced-by-count":3,"title":["Linear time algorithms for approximating the facility terminal cover problem"],"prefix":"10.1002","volume":"50","author":[{"given":"Guang","family":"Xu","sequence":"first","affiliation":[]},{"given":"Yang","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Jinhui","family":"Xu","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,5,2]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90072-H"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"S.Arora S.Rao U.Vazirani Expander flows geometric embeddings and graph partitioning Proceedings of Symposium on the Theory of Computing 2004.","DOI":"10.1145\/1007352.1007355"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(81)90020-1"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-0208(08)73101-3"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02798690"},{"key":"e_1_2_1_7_2","unstructured":"M.Charikar J.Naor B.Scieber Resource optimization in QoS multicast routing of real\u2010time multimedia Proceedings 19th Annual IEEE INFOCOM Tel Aviv Israel 2000 pp.1518\u20131527."},{"key":"e_1_2_1_8_2","unstructured":"J.Chuzhoy J.Naor Covering problems with hard capacities Proceedings of Symposium on Foundations of Computer Science Vancouver BC Canada 2002 pp.481\u2013489."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","DOI":"10.1145\/509907.509915","volume-title":"The importance of being biased","author":"Dinur I.","year":"2002"},{"key":"e_1_2_1_11_2","first-page":"164","volume-title":"An improved approximation algorithm for vertex cover with hard capacities","author":"Gandhi R.","year":"2003"},{"key":"e_1_2_1_12_2","first-page":"323","volume-title":"Dependent rounding in bipartite graphs","author":"Gandhi R.","year":"2002"},{"key":"e_1_2_1_13_2","volume-title":"Computers and intractability: A guide to the theory of NP\u2010completeness","author":"Garay M.R.","year":"1979"},{"key":"e_1_2_1_14_2","unstructured":"T.F.Gonzalez A simple LP\u2010free approximation algorithm for the minimum weight vertex cover problem Technique Report 1993\u201018 Department of Computer Science University of California at Santa Barbara Santa Barbara CA 1993."},{"key":"e_1_2_1_15_2","first-page":"858","volume-title":"Capacitated vertex covering with applications","author":"Guha S.","year":"2002"},{"key":"e_1_2_1_16_2","volume-title":"Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs","author":"Halperin E.","year":"2000"},{"key":"e_1_2_1_17_2","first-page":"289","volume-title":"The minimum generalized vertex cover problem","author":"Hassin R.","year":"2005"},{"key":"e_1_2_1_18_2","first-page":"1","volume-title":"Some optimal inapproximability results","author":"H\u00e5stad J.","year":"1997"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211045"},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","DOI":"10.1007\/11523468_84","volume-title":"A better approximation ratio for the vertex cover problem","author":"Karakostas G.","year":"2005"},{"key":"e_1_2_1_21_2","unstructured":"M. Kawabe"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00290149"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90151-1"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_1_25_2","volume-title":"Issues with multicast video distribution in heterogeneous packet networks","author":"Turletti T.","year":"1994"},{"key":"e_1_2_1_26_2","article-title":"Constant approximation algorithms for rectangle stabbing and related problems","author":"Xu G.","journal-title":"Theor Comput Syst"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.20172","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.20172","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,14]],"date-time":"2023-11-14T22:50:19Z","timestamp":1700002219000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.20172"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5,2]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2007,8]]}},"alternative-id":["10.1002\/net.20172"],"URL":"https:\/\/doi.org\/10.1002\/net.20172","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,5,2]]}}}