Coordination complexity of parallel price-directive decomposition

Coordination complexity of parallel price-directive decomposition

0.00 Avg rating0 Votes
Article ID: iaor2004920
Country: United States
Volume: 21
Issue: 2
Start Page Number: 321
End Page Number: 340
Publication Date: May 1996
Journal: Mathematics of Operations Research
Authors: ,
Abstract:

The general block-angular convex resource sharing problem in K blocks and M nonnegative block-separable coupling constraints is considered. Applications of this model are in combinatorial optimization, network flows, scheduling, communication networks, engineering design, and finance. This paper studies the coordination complexity of approximate price-directive decomposition (PDD) for this problem, i.e., the number of iterations required to solve the problem to a fixed relative accuracy as a function of K and M. First a simple PDD method based on the classical logarithmic potential is shown to be optimal up to a logarithmic factor in M in the class of all PDD methods that work with the original (unrestricted) blocks. It is then shown that logarithmic and exponential potentials generate a polylogarithmically-optimal algorithm for a wider class of PDD methods which can restrict the blocks by the coupling constraints. As an application, the fastest currently-known deterministic approximation algorithm for minimum-cost multi-commodity flows is obtained.

Reviews

Required fields are marked *. Your email address will not be published.