Local algorithms and max-min linear programs

A local algorithm is a distributed algorithm that completes in constant time (constant number of synchronous communication rounds), independent of the size of the network. In a local algorithm, the output of a node can only depend on the input available within its constant-radius neighbourhood; therefore a local algorithm is highly fault-tolerant, as the effect of a topology change is confined to a constant-radius part of the network.

In our work, we study local algorithms for max-min linear programs, where the objective is to

maximise w
subject to Ax <= 1, Cx >= w1, x >= 0.

Here the matrices A and C are nonnegative and sparse. Each row of A has at most Delta_I positive elements, and each row C has at most Delta_K positive elements; Delta_I > 1 and Delta_K > 1 are constants.

We show that in a distributed setting, there is a sharp threshold

alpha = Delta_I (1 - 1/Delta_K)

for the local approximability of max-min linear programs. We prove that there is no local algorithm with the approximation ratio alpha. We also present a local algorithm that achieves the approximation ratio of alpha + epsilon; we can make the constant epsilon > 0 arbitrarily small at the cost of increased running time.

This is joint work with Patrik Floréen, Marja Hassinen, Joel Kaasinen, Petteri Kaski, and Topi Musto.