Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems

Ta Duy Nguyen, Alina Ene

We study the densest subgraph problem and give algorithms via multiplicative weights update and area convexity that converge in $O\left(\frac{\log m}{{\epsilon }^2}\right)$ and $O\left(\fr…