Distributed combinatorial optimization - Extended Abstract
Fabian Kühn, Roger P. Wattenhofer · Repository for Publications and Research Data (ETH Zurich) · 2005
Approximating integer linear programs by solving a relaxation to a linear program (LP) and afterwards reconstructing an integer solution from the fractional one is a standard technique in a non-distributed scenario.Surprisingly, the method has not often been applied for distributed algorithms.In this paper, we show that LP relaxation is a powerful technique also to obtain fast distributed approximation algorithms.We present a novel deterministic distributed algorithm which computes a constant factor approximates for fractional covering and packing problems in only log 2 rounds, using messages of logarithmic size.If messages are allowed to be larger, we show that a constant approximation can be achieved in a logarithmic number of rounds only.Finally, we show that by combining our LP approximation algorithms with randomized rounding techniques, we obtain efficient distributed approximation algorithms for a number of combinatorial problems.