Algosensors 2008 · 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks, Reykjavík, Iceland, July 2008 · doi:10.1007/978-3-540-92862-1_2
Algosensors 2008 Best Paper Award
In a bipartite max-min LP, we are given a bipartite graph G = (V ∪ I ∪ K, E), where each agent v ∈ V is adjacent to exactly one constraint i ∈ I and exactly one objective k ∈ K. Each agent v controls a variable xv. For each i ∈ I we have a nonnegative linear constraint on the variables of adjacent agents. For each k ∈ K we have a nonnegative linear objective function of the variables of adjacent agents. The task is to maximise the minimum of the objective functions. We study local algorithms where each agent v must choose xv based on input within its constant-radius neighbourhood in G. We show that for every ε ≥ 0 there exists a local algorithm achieving the approximation ratio ΔI (1 − 1/ΔK) + ε. We also show that this result is the best possible – no local algorithm can achieve the approximation ratio ΔI (1 − 1/ΔK). Here ΔI is the maximum degree of a vertex i ∈ I, and ΔK is the maximum degree of a vertex k ∈ K. As a methodological contribution, we introduce the technique of graph unfolding for the design of local approximation algorithms.
Sándor P. Fekete (Ed.): Algorithmic Aspects of Wireless Sensor Networks, Fourth International Workshop, ALGOSENSORS 2008, Reykjavik, Iceland, July 2008, Revised Selected Papers, volume 5389 of Lecture Notes in Computer Science, pages 2–17, Springer, Berlin, 2008
ISBN 978-3-540-92861-4