Tight local approximation results for max-min linear programs

In a bipartite max-min LP, we are given a bipartite graph $\myG = (V \cup I \cup K, E)$,whereeachagent$v \in V$isadjacenttoexactlyoneconstraint$i \in I$andexactlyoneobjective$k \in K$\mathrm{.}Eachagent$v$ controls a variable $x_v$. For each $i\in I$ we have a nonnegative linear constraint on the variables of adjacent agents. For each $k\in K$ we have a nonnegative linear objective function of the variables of adjacent agents. The task is to maximise the minimum of the objective functions. We study local algorithms where each agent $v$ must choose $x_v$ based on input within its constant-radius neighbourhood in $\text{myG}$. We show that for every $ϵ>0$ there exists a local algorithm achieving the approximation ratio ${\Delta_I (1

• 1/\Delta_K)} + \epsilon$. We also show that this result is the best possible – no local algorithm can achieve the approximation ratio ${\Delta_I (1 - 1/\Delta_K)}$\mathrm{.}Here$\Delta_I$isthemaximumdegreeofavertex$i \in I$,and$\Delta_K$isthemaximumdegreeofavertex$k \in K$. As a methodological contribution, we introduce the technique of graph unfolding for the design of local approximation algorithms.