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 Sigmav CkvXv subject to Sigma_v alphaivXv les 1 far each i and Xv ges 0 far each v. Here c_kv ges 0, and the support sets V_i = {v : alphaiv> 0}, V_k = {v : c_kv > 0}, I_v = {i: alpha_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.