The Multiplicative Weights Update Method: a Meta-Algorithm and Applications

Authors: Sanjeev Arora, Elad Hazan, Satyen Kale - ACM Symposium on Theory of Computing, STOC 2005 cited by 925

Algorithms in varied fields use the idea of maintaining a distribution over a certain set and use the multiplicative update rule to iteratively change these weights. Their analyses are usually very similar and rely on an exponential potential function. In this survey we present a simple meta-algorithm that unifies many of these disparate algorithms and derives them as simple instantiations of the meta-algorithm. We feel that since this meta-algorithm and its analysis are so simple, and its applications so broad, it should be a standard part of algorithms courses, like “divide and conquer.”