Externalities in Online Advertising

Опубликовано 8 сентября 2016, 18:54

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.