Approximating minimum power edge-multi-covers

Nachshon Cohen () and Zeev Nutov ()
Additional contact information
Nachshon Cohen: The Open University of Israel
Zeev Nutov: The Open University of Israel

Journal of Combinatorial Optimization, 2015, vol. 30, issue 3, No 10, 563-578

Abstract: Abstract 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 $$G=(V,E)$$ G = ( V , E ) with edge costs and lower degree bounds $$\{r(v):v \in V\}$$ { r ( v ) : v ∈ V } , the Min-Power Edge-Multicover problem is to find a minimum-power subgraph $$J$$ J of $$G$$ G such that the degree of every node $$v$$ v in $$J$$ J is at least $$r(v)$$ r ( v ) . Let $$k=\max _{v \in V} r(v)$$ k = max v ∈ V r ( v ) . For $$k=\Omega (\log n)$$ k = Ω ( log n ) , the previous best approximation ratio for the problem was $$O(\log n)$$ O ( log n ) , even for uniform costs (Kortsarz et al. 2011). Our main result improves this ratio to $$O(\log k)$$ O ( log k ) for general costs, and to $$O(1)$$ O ( 1 ) for uniform costs. This also implies ratios $$O(\log k)$$ O ( log k ) for the Min-Power $$k$$ k -Outconnected Subgraph and $$O\left( \log k \log \frac{n}{n-k} \right) $$ O log k log n n - k for the Min-Power $$k$$ k -Connected Subgraph problems; the latter is the currently best known ratio for the min-cost version of the problem when $$n \le k{(k-1)}^2$$ n ≤ k ( k - 1 ) 2 . In addition, for small values of $$k$$ k , we improve the previously best ratio $$k+1$$ k + 1 to $$k+1/2$$ k + 1 / 2 .

Keywords: Wireless networks; Edge multi-cocer; Graph connectivity; Approximation algorithms (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9652-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:3:d:10.1007_s10878-013-9652-6

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9652-6

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().