Theory of Computing
-------------------
Title : The Multiplicative Weights Update Method: a Meta-Algorithm and Applications
Authors : Sanjeev Arora, Elad Hazan, and Satyen Kale
Volume : 8
Number : 6
Pages : 121-164
URL : http://www.theoryofcomputing.org/articles/v008a006
Abstract
--------
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."