2008/06/02 by Patrik Floréen, Marja Hassinen, Floréen, Patrik +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.0806.0282
openalex publication_date 2008/06/02 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/02
We study the applicability of distributed, local algorithms to 0/1 max-min LPs where the objective is to maximise mink ∑v ckv xv subject to ∑v aiv xv ≤ 1 for each i and xv ≥ 0 for each v. Here ckv ∈ \0,1\, aiv ∈ \0,1\, and the support sets Vi = \v : aiv > 0 \ and Vk = \v : ckv>0 \ have bounded size; in particular, we study the case |Vk| ≤ 2. Each agent v is responsible for choosing the value of xv based on information within its constant-size neighbourhood; the communication network is the hypergraph where the sets Vk and Vi constitute the hyperedges. We present a local approximation algorithm which achieves an approximation ratio arbitrarily close to the theoretical lower bound presented in prior work.