Details

Autor(en) / Beteiligte

• Gehweiler, Joachim
• Lammersen, Christiane
• Sohler, Christian

Titel

A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem

Ist Teil von

• Algorithmica, 2014-03, Vol.68 (3), p.643-670

Ort / Verlag

Boston: Springer US

Erscheinungsjahr

2014

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We investigate a metric facility location problem in a distributed setting. In this problem, we assume that each point is a client as well as a potential location for a facility and that the opening costs for the facilities and the demands of the clients are uniform. The goal is to open a subset of the input points as facilities such that the accumulated cost for the whole point set, consisting of the opening costs for the facilities and the connection costs for the clients, is minimized. We present a randomized distributed algorithm that computes in expectation an -approximate solution to the metric facility location problem described above. Our algorithm works in a synchronous message passing model, where each point is an autonomous computational entity that has its own local memory and that communicates with the other entities by message passing. We assume that each entity knows the distance to all the other entities, but does not know any of the other pairwise distances. Our algorithm uses three rounds of all-to-all communication with message sizes bounded to bits, where n is the number of input points. We extend our distributed algorithm to constant powers of metric spaces. For a metric exponent ℓ ≥1, we obtain a randomized -approximation algorithm that uses three rounds of all-to-all communication with message sizes bounded to bits.