Approximating minimum power edge-multi-covers

作者：Cohen Nachshon; Nutov Zeev^*

来源：Journal of Combinatorial Optimization, 2015, 30(3): 563-578.

DOI：10.1007/s10878-013-9652-6

• Wireless networks
• Edge multi-cocer
• Graph connectivity
• Approximation algorithms

Given an undirected graph with edge costs, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider the following fundamental problem that arises in wireless network design. Given a graph with edge costs and lower degree bounds , the Min-Power Edge-Multicover problem is to find a minimum-power subgraph of such that the degree of every node in is at least . Let . For , the previous best approximation ratio for the problem was , even for uniform costs (Kortsarz et al. 2011). Our main result improves this ratio to for general costs, and to for uniform costs. This also implies ratios for the Min-Power -Outconnected Subgraph and for the Min-Power -Connected Subgraph problems; the latter is the currently best known ratio for the min-cost version of the problem when . In addition, for small values of , we improve the previously best ratio to k + 1 to k + 1/2.

• 出版日期2015-10