Patrik Floréen · Marja Hassinen · Petteri Kaski · Jukka Suomela

Tight local approximation results for max-min linear programs

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

authors’ version publisher’s version


In a bipartite max-min LP, we are given a bipartite graph G = (V ∪ I ∪ KE), 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


Journal Version

© Springer 2008

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.