---
res:
bibo_abstract:
- 'We present two distributed, constant factor approximation algorithms for the
metric facility location problem. Both algorithms have been designed with a strong
emphasis on applicability in the area of wireless sensor networks: in order to
execute them, each sensor node only requires limited local knowledge and simple
computations. Also, the algorithms can cope with measurement errors and take into
account that communication costs between sensor nodes do not necessarily increase
linearly with the distance, but can be represented by a polynomial. Since it cannot
always be expected that sensor nodes execute algorithms in a synchronized way,
our algorithms are executed in an asynchronous model (but they are still able
to break symmetry that might occur when two neighboring nodes act at exactly the
same time). Furthermore, they can deal with dynamic scenarios: if a node moves,
the solution is updated and the update affects only nodes in the local neighborhood.
Finally, the algorithms are robust in the sense that incorrect behavior of some
nodes during some round will, in the end, still result in a good approximation.
The first algorithm runs in expected O(log_{1+\epsilon} n) communication rounds
and yields a \my^4(1+4\my^2(1+\epsilon)^{1/p})^p approximation, while the second
has a running time of expected O(log^2_{1+\epsilon} n) communication rounds and
an approximation factor of \my^4(1 + 2(1 + \epsilon)^{1/p})^p. Here, \epsilon
> 0 is an arbitrarily small constant, p the exponent of the polynomial representing
the communication costs, and \my the relative measurement error.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sebastan
foaf_name: Abshoff, Sebastan
foaf_surname: Abshoff
- foaf_Person:
foaf_givenName: Andreas
foaf_name: Cord-Landwehr, Andreas
foaf_surname: Cord-Landwehr
- foaf_Person:
foaf_givenName: Bastian
foaf_name: Degener, Bastian
foaf_surname: Degener
- foaf_Person:
foaf_givenName: 'Barbara '
foaf_name: 'Kempkes, Barbara '
foaf_surname: Kempkes
- foaf_Person:
foaf_givenName: Peter
foaf_name: Pietrzyk, Peter
foaf_surname: Pietrzyk
bibo_doi: 10.1007/978-3-642-28209-6_3
dct_date: 2011^xs_gYear
dct_language: eng
dct_title: Local Approximation Algorithms for the Uncapacitated Metric Facility
Location Problem in Power-Aware Sensor Networks@
...