Patrik Floréen · Petteri Kaski · Topi Musto · Jukka Suomela

Approximating max-min linear programs with local algorithms

IPDPS 2008 · 22nd IEEE International Parallel & Distributed Processing Symposium, Miami, FL, USA, April 2008 · doi:10.1109/IPDPS.2008.4536235

authors’ version publisher’s version


A local algorithm is a distributed algorithm where each node must operate solely based on the information that was available at system startup within a constant-size neighbourhood of the node. We study the applicability of local algorithms to max-min LPs where the objective is to maximise mink Σv ckvxv subject to Σv aivxv ≤ 1 for each i and xv ≥ 0 for each v. Here ckv ≥ 0, aiv ≥ 0, and the support sets Vi = { v : aiv ≥ 0 }, Vk = { v :  ckv ≥ 0 }, Iv = { i : aiv ≥ 0 } and Kv = { k : ckv ≥ 0 } have bounded size. In the distributed setting, each agent v is responsible for choosing the value of xv, and the communication network is a hypergraph H where the sets Vk and Vi constitute the hyperedges. We present inapproximability results for a wide range of structural assumptions; for example, even if |Vi| and |Vk| are bounded by some constants larger than 2, there is no local approximation scheme. To contrast the negative results, we present a local approximation algorithm which achieves good approximation ratios if we can bound the relative growth of the vertex neighbourhoods in H.


Proceedings of the 2008 IEEE International Parallel & Distributed Processing Symposium, IPDPS 2008, Program Book and CD-ROM, IEEE, Piscataway, 2008

ISBN 978-1-4244-1694-3


Journal Version

© IEEE 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.