IPDPS 2008 · 22nd IEEE International Parallel & Distributed Processing Symposium, Miami, FL, USA, April 2008 · doi:10.1109/IPDPS.2008.4536235
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