Multiplicative Weights: An Elegant Application to Maximum Flow

Abstract

Multiplicative weights is a class of meta-algorithms commonly found in learning theory. It typically carries out several rounds of queries to oracles/agents, each time learning weights in an online manner given feedback from the current system to capture proficiency of them. It has found its use in game theory, machine learning, fast algorithms for optimization, etc. We begin with the classical example of multiplicative weights weighted majority. In the second part, we will see a delicate usage of multiplicative weights for approximating the maximum network flow, a well-known problem in theoretical computer science with many practical usages, accompanied by visualization from our simulation. The algorithm approximates maximum flow by repeatedly solving a related, computationally easier problem, the electrical flow of a circuit, whose parameters are derived from multiplicative weights. Multiplicative weights come in to adjust the resistances of the circuit online so that edge capacities are gradually obeyed. It is an elegant piece of work drawing insights
from learning theory, physics, numerical methods, and theoretical computer science.
This journal is intended for undergraduate readers broadly interested in mathematics and theoretical computer science, who have developed some mathematical maturity and are familiar with basic algorithms.