Coordination Complexity of Parallel Price-Directive Decomposition

Autor:	Michael D. Grigoriadis, Leonid Khachiyan
Rok vydání:	1996
Předmět:	Mathematical optimization Logarithm General Mathematics Regular polygon Combinatorial optimization Approximation algorithm Management Science and Operations Research Flow network Computer Science Applications Exponential function Scheduling (computing) Mathematics Nonlinear programming
Zdroj:	Mathematics of Operations Research. 21:321-340
ISSN:	1526-5471 0364-765X
DOI:	10.1287/moor.21.2.321
Popis:	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.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::1be388f756ee518088d5e3dd2123ff57 https://doi.org/10.1287/moor.21.2.321 Zobrazit plný text záznamu Plný text ve formátu PDF