Coordination Complexity of Parallel Price-Directive Decomposition
Coordination Complexity of Parallel Price-Directive Decomposition
复制标题
并行价格指令分解的协调复杂度
DOI：
--
复制
发表时间：
1996
影响因子：
1.7
通讯作者：
L. Khachiyan
中科院分区：
文献类型：
--
作者：
M. Grigoriadis;L. Khachiyan
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 multicommodity flows is obtained.
