2007/10/08 by Patrik Floréen, Petteri Kaski, Topi Musto +1 · 14 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Algorithm #Artificial intelligence #Complexity and Algorithms in Graphs #Computer science #Optimization and Search Problems #cs.DC
paper · pdf · doi:10.1109/ipdps.2008.4536235
published in Proceedings - IEEE International Parallel and Distributed Processing Symposium, 1-10 (Institute of Electrical and Electronics Engineers) · 16 pages, 2 figures
arxiv created 2007/10/08 · openalex publication_date 2008/04/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 minkSigmav CkvXv subject to SigmavalphaivXv les 1 far each i and Xv ges 0 far each v. Here ckvges 0, and the support sets Vi= v : alphaiv> 0, Vk= v : ckv> 0, Iv= i: alphaiv> 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 Vkand Viconstitute 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.