This paper studies the coordination complexity of PDD approximation
methods, i.e., the number of iterations required to solve the general
resource sharing problem to a fixed relative accuracy, as a function
of $K$ and $M$. First, a simple PDD method based on the classical
logarithmic potential function is presented and analyzed. For a fixed
accuracy, its coordination complexity is shown to be $O(M\ln M)$,
which is within a logarithmic factor of the best possible bound for
any PDD method that works with the original blocks. An important
property of the logarithmic-potential PDD method is that its
coordination complexity depends neither on the ``width'' nor on the
dimension of the blocks. Second, polylogarithmically-matching upper
and lower coordination complexity bounds are presented for a wider
class of PDD methods in which each block can be partially restricted
by the coupling constraints. The upper bound for this class of PDD is
obtained by a combined method, which uses either the logarithmic or
the exponential potential function, depending on the number of
coupling constraints per block.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-19.ps
DIMACS Home Page