conference paper
Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks
Sebastan
Abshoff
author
Andreas
Cord-Landwehr
author
Bastian
Degener
author
Barbara
Kempkes
author
Peter
Pietrzyk
author
63
department
SFB 901
project
SFB 901 - Subprojekt A1
project
SFB 901 - Project Area A
project
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.
https://ris.uni-paderborn.de/download/657/1219/657-flp_algosensors2011-Cord-Landwehr.pdf
application/pdf
2011
eng
Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS)10.1007/978-3-642-28209-6_3
13-27
Abshoff, Sebastan, et al. “Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks.” <i>Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS)</i>, 2011, pp. 13–27, doi:<a href="https://doi.org/10.1007/978-3-642-28209-6_3">10.1007/978-3-642-28209-6_3</a>.
Abshoff, S., Cord-Landwehr, A., Degener, B., Kempkes, B., & Pietrzyk, P. (2011). Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks. In <i>Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS)</i> (pp. 13–27). <a href="https://doi.org/10.1007/978-3-642-28209-6_3">https://doi.org/10.1007/978-3-642-28209-6_3</a>
Abshoff S, Cord-Landwehr A, Degener B, Kempkes B, Pietrzyk P. Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks. In: <i>Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS)</i>. LNCS. ; 2011:13-27. doi:<a href="https://doi.org/10.1007/978-3-642-28209-6_3">10.1007/978-3-642-28209-6_3</a>
@inproceedings{Abshoff_Cord-Landwehr_Degener_Kempkes_Pietrzyk_2011, series={LNCS}, title={Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks}, DOI={<a href="https://doi.org/10.1007/978-3-642-28209-6_3">10.1007/978-3-642-28209-6_3</a>}, booktitle={Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS)}, author={Abshoff, Sebastan and Cord-Landwehr, Andreas and Degener, Bastian and Kempkes, Barbara and Pietrzyk, Peter}, year={2011}, pages={13–27}, collection={LNCS} }
Abshoff, Sebastan, Andreas Cord-Landwehr, Bastian Degener, Barbara Kempkes, and Peter Pietrzyk. “Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks.” In <i>Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS)</i>, 13–27. LNCS, 2011. <a href="https://doi.org/10.1007/978-3-642-28209-6_3">https://doi.org/10.1007/978-3-642-28209-6_3</a>.
S. Abshoff, A. Cord-Landwehr, B. Degener, B. Kempkes, and P. Pietrzyk, “Local Approximation Algorithms for the Uncapacitated Metric Facility Location Problem in Power-Aware Sensor Networks,” in <i>Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS)</i>, 2011, pp. 13–27.
S. Abshoff, A. Cord-Landwehr, B. Degener, B. Kempkes, P. Pietrzyk, in: Proceedings of the 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS), 2011, pp. 13–27.
6572017-10-17T12:43:00Z2019-04-11T13:41:14Z