A simple analysis of multiplicative weights

I give a clean and self-contained presentation of the multiplicative weights framework that is somewhat more direct than the most popular analysis (see the comparison below). The framework provides a simple algorithm for (approximately) solving many important problems (e.g., maximum flow, densest subgraph, linear classification, zero-sum games and even general linear programs) and is a beautiful demonstration of leveraging continuous analysis to solve discrete problems. Warning: this is a technical post.

Read More