Local approximation algorithms for a class of 0/1 max-min linear programs

Abstract

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.

7 pages, 3 figures

References in corpus (1)

• Approximating max-min linear programs with local algorithms