Tight local approximation results for max-min linear programs

In a bipartite max-min LP, we are given a bipartite graph G = (V ∪ I ∪ K, E), where each agent v ∈ V is adjacent to exactly one constraint i ∈ I and exactly one objective k ∈ K. Each agent v controls a variable x_v. For each i ∈ I we have a nonnegative linear constraint on the variables of adjacent agents. For each k ∈ 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 G. We show that for every ε ≥ 0 there exists a local algorithm achieving the approximation ratio Δ_I (1 − 1/Δ_K) + ε. We also show that this result is the best possible – no local algorithm can achieve the approximation ratio Δ_I (1 − 1/Δ_K). Here Δ_I is the maximum degree of a vertex i ∈ I, and Δ_K is the maximum degree of a vertex k ∈ K. As a methodological contribution, we introduce the technique of graph unfolding for the design of local approximation algorithms.