A fundamental class of problems in wireless communication is concerned with the assignment of suitable transmission powers
to wireless devices/stations such that the resulting communication graph satisfies certain desired properties and the overall
energy consumed is minimized. Many concrete communication tasks in a wireless network like broadcast, multicast, point-to-point
routing, creation of a communication backbone, etc. can be regarded as such a power assignment problem.
This paper considers several problems of that kind; the first problem was studied before in [1,6] and aims to select and assign
powers to
k out of a total of
n wireless network stations such that all stations are within reach of at least one of the selected stations. We show that
the problem can be (1 +
ε) approximated by only looking at a small subset of the input, which is of size
n((a/e)O(d))n^{((\alpha/\epsilon)^{O(d)})}
for the algorithm by Bilo et al. at ESA’05 ([6]) actually obtaining a running time that is
linear in
n. Furthermore we sketch how outliers can be handled in our coreset construction.
The second problem deals with the energy-efficient, bounded-hop multicast operation: Given a subset C out of a set of n stations and a designated source node s we want to assign powers to the stations such that every node in C is reached by a transmission from s within k hops. Again we show that a coreset of size independent of n and polynomial in k, |C|, 1/ε exists, and use this to provide an algorithm which runs in time linear in n.
The last problem deals with a variant of non-metric TSP problem where the edge costs are the squared Euclidean distances;
this problem is motivated by data aggregation schemes in wireless sensor networks. We show that a good TSP tour under Euclidean
edge costs can be very bad in the squared distance measure and provide a simple constant approximation algorithm, partly improving
upon previous results in [5], [4].