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

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 *x*_{v}. 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 *x*_{v} 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

- Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, Topi Musto, and Jukka Suomela: Local approximability of max-min and min-max linear programs ·
*Theory of Computing Systems*49:672–697, 2011