Power Assignment Problems in Wireless Communication
This paper considers several problems in the area of wireless communication.
Peter Pan
Introduction
Wireless network technology has gained tremendous importance in recent years.
It not only opens new application areas with the availability of high-bandwidth connections
for mobile devices, but also more and more replaces so far 'wired' network installations.
Related Work
The k-Station Network Coverage problem was considered by Bilo et al.
Our Contribution
We make progress for the considered problems in two respects:
we show how to find a coreset of size independent of n.
we provide an exact algorithm for the problem reduced on the coreset
Preliminaries
Given a set S of points and some constant k, we want to find
at most k d-dimensional balls with radii ri that cover all points in
S while minimizing the sum of powers.
Information Aggregation via TSP Tours
In this section we show that the normal Euclidean TSP is
not suitable for obtaining an energy-efficient tour
and devise a 6-approximation algorithm for TSP under squared Euclidean metric.
References
Asterix: Energy-minimal TSP-Tours in Northern France, 2008
Obelix: Faster Algorithms with Hinkelstones, 2007