Title: Stateless Distributed Gradient Descent for Positive Linear Programs

Speaker: Rohit Khandekar, IBM Watson 

Abstract:

I shall describe a framework of distributed and stateless solutions
for packing and covering linear programs, which are solved by multiple
agents operating in a cooperative but uncoordinated manner. Our model
has a separate "agent" controlling each variable and an agent is
allowed to read-off the current values only of those constraints in
which it has non-zero coefficients. This is a natural model for many
distributed applications like multi-commodity flow control, maximum
bipartite matching, and dominating sets.

The most appealing feature of our algorithms is their simplicity and
fast convergence. For example, in the case of the flow control
problem, our algorithm associates edge-lengths that are exponential in
the edge-congestions and each commodity increases (or decreases) its
flow multiplicatively if its path-length is less (or more) than a
threshold. Our algorithm starting from any feasible solution, always
maintains feasibility, and converges to a near-optimum solution in
poly-logarithmic time.

While exponential dual variables are used in several packing/ covering
LP algorithms before, this is the first algorithm which is both
stateless and has poly-logarithmic convergence. Our algorithms can be
thought of as applying distributed gradient descent/ascent on a
carefully chosen potential.

This talk is based on a joint work with Baruch Awerbuch that appeared
in STOC 08.