Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Accelerating the Multiplicative-Weights Framework for Graph Linear Programs

Simons Institute via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore an advanced lecture on accelerating the multiplicative-weight updates (MWU) framework for solving packing and covering linear programs in graph optimization. Delve into the innovative approach of replacing the standard MWU iteration with a packing version of the Min-Inner-Product oracle. Discover how this modification significantly reduces the number of iterations required for an ε-approximate solution from Θ(m) to ~Θ(√m). Examine the potential for breaking the O(mn) runtime barrier in basic Network design LPs, such as Min Steiner Cut, by leveraging faster solutions to the Packing problem. Gain insights from the collaborative research of Omri Weinstein, Zhuan Khye Koh, and Sorrachai Yingchareonthawornchai, presented at the Simons Institute's Dynamic Graphs and Algorithm Design program.

Syllabus

Accelerating the Multiplicative-Weights Framework for Graph Linear Programs

Taught by

Simons Institute

Reviews

Start your review of Accelerating the Multiplicative-Weights Framework for Graph Linear Programs

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.