Local approximability of max-min and min-max linear programs

In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0. In a min-max LP, the objective is to minimise ρ subject to Ax ≤ ρ1, Cx ≥ 1, and x ≥ 0. The matrices A and C are nonnegative and sparse: each row a_i of A has at most Δ_I positive elements, and each row c_k of C has at most Δ_K positive elements. We study the approximability of max-min LPs and min-max LPs in a distributed setting; in particular, we focus on local algorithms (constant-time distributed algorithms). We show that for any Δ_I ≥ 2, Δ_K ≥ 2, and ε > 0 there exists a local algorithm that achieves 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) for any Δ_I ≥ 2 and Δ_K ≥ 2.