Approximating max-min linear programs with local algorithms

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 min_k Σ_v c_kvx_v subject to Σ_v a_ivx_v ≤ 1 for each i and x_v ≥ 0 for each v. Here c_kv ≥ 0, a_iv ≥ 0, and the support sets V_i = { v : a_iv ≥ 0 }, V_k = { v :  c_kv ≥ 0 }, I_v = { i : a_iv ≥ 0 } and K_v = { k : c_kv ≥ 0 } have bounded size. In the distributed setting, each agent v is responsible for choosing the value of x_v, and the communication network is a hypergraph H where the sets V_k and V_i constitute the hyperedges. We present inapproximability results for a wide range of structural assumptions; for example, even if |V_i| and |V_k| 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.