Externalities in Online Advertising

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.

Speaker Details

Rohit Khandekar is a Research Staff Member in the department of Data Intensive Systems and Analytics at IBM T.J. Watson research center. Previously, he has worked at UC Berkeley and U Waterloo as a post-doctoral researcher. His research interests include theoretical and practical aspects related to combinatorial optimization, approximation algorithms, algorithmic game theory, and mathematical programming.

Date:
Speakers:
Rohit Khandekar
Affiliation:
IBM, Watson