[BigDataX] Diptodip Deb Title & Abstract
diptodipdeb at gatech.edu
Fri Jul 8 13:13:05 CDT 2016
Improved Algorithms for Two Energy-Optimal Routing Problems in Ad-Hoc Wireless Networks
We study two problems of assigning transmission power to the nodes of ad hoc wireless networks to minimize total power consumption while satisfying certain connectivity constraints. The first problem requires to establish k node-disjoint paths from a given source to a given destination. Our new algorithm works for the most general cost model, and returns an optimal solution in time O(n3) (where n is the number of nodes), improving the running time over the previously published algorithm by a factor of k.
The second problem assumes that the power requirement between any two nodes is symmetric, and that there are exactly two possible power levels, one of which is negligible. A source is given and all the nodes in the network must be reachable from the source (unidirectional links allowed for broadcast). We obtain a (4 + ln n)-approximation algorithm, while the best published approximation ratio is 2(1 + ln(n ? 1)). It was also known that no approximation ratio better than O(lnn) is possible unless P =NP.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the bigdatax