Local approximation algorithms for a class of 0/1 max-min linear programs
| dc.creator | Floréen, Patrik | |
| dc.creator | Hassinen, Marja | |
| dc.creator | Kaski, Petteri | |
| dc.creator | Suomela, Jukka | |
| dc.date | 2008-06-02 | |
| dc.date.accessioned | 2026-07-07T12:19:20Z | |
| dc.date.available | 2026-07-07T12:19:20Z | |
| dc.description | We study the applicability of distributed, local algorithms to 0/1 max-min LPs where the objective is to maximise ${\min_k \sum_v c_{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} \in \{0,1\}$, $a_{iv} \in \{0,1\}$, and the support sets ${V_i = \{v : a_{iv} > 0 \}}$ and ${V_k = \{v : c_{kv}>0 \}}$ have bounded size; in particular, we study the case $|V_k| \le 2$. Each agent $v$ is responsible for choosing the value of $x_v$ based on information within its constant-size neighbourhood; the communication network is the hypergraph where the sets $V_k$ and $V_i$ 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. | |
| dc.description | 7 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/0806.0282 | |
| dc.identifier | http://arxiv.org/abs/0806.0282 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/212718 | |
| dc.subject | Distributed, Parallel, and Cluster Computing | |
| dc.title | Local approximation algorithms for a class of 0/1 max-min linear programs | |
| dc.type | text |