Loading...
Please wait, while we are loading the content...
Similar Documents
Distributed combinatorial optimization (extended abstract).
| Content Provider | CiteSeerX |
|---|---|
| Author | Wattenhofer, Roger Kuhn, Fabian |
| Abstract | 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 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. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Lp Relaxation Distributed Approximation Algorithm Extended Abstract Combinatorial Optimization Integer Solution Linear Program Log Round Approximation Algorithm Fractional One Constant Approximation Distributed Algorithm Standard Technique Logarithmic Number Integer Linear Program Non-distributed Scenario Fractional Covering Powerful Technique Logarithmic Size Combinatorial Problem Lp Approximation Algorithm Constant Factor Approximates |
| Content Type | Text |
