Approximating max-min linear programs with local algorithms - Computer Science > Distributed, Parallel, and Cluster ComputingReportar como inadecuado




Approximating max-min linear programs with local algorithms - Computer Science > Distributed, Parallel, and Cluster Computing - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: A local algorithm is a distributed algorithm where each node must operatesolely based on the information that was available at system startup within aconstant-size neighbourhood of the node. We study the applicability of localalgorithms to max-min LPs where the objective is to maximise $\min k \sum vc {kv} x v$ subject to $\sum v a {iv} x v \le 1$ for each $i$ and $x v \ge 0$for each $v$. Here $c {kv} \ge 0$, $a {iv} \ge 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 thecommunication network is a hypergraph $\mathcal{H}$ where the sets $V k$ and$V i$ constitute the hyperedges. We present inapproximability results for awide 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 approximationscheme. To contrast the negative results, we present a local approximationalgorithm which achieves good approximation ratios if we can bound the relativegrowth of the vertex neighbourhoods in $\mathcal{H}$.



Autor: Patrik Floréen, Petteri Kaski, Topi Musto, Jukka Suomela

Fuente: https://arxiv.org/







Documentos relacionados