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

YouTube

A Simple -Approximation Adaptive Sketching Algorithm for Maximum Weighted Matching

Simons Institute via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore a 47-minute lecture by Sepehr Assadi from the University of Waterloo and Rutgers University, presented at the Simons Institute. Delve into a simple algorithm for computing (1-eps)-approximation of weighted matching in general graphs using O(log(n)/eps) rounds of adaptive sketching. Learn how this approach matches state-of-the-art algorithms while offering greater simplicity. Discover the algorithm's reliance on a "white-box" application of the multiplicative weight update method, featuring a self-contained primal-dual analysis that may be of broader interest. Gain insights into advanced concepts in sketching and algorithm design for maximum weighted matching problems.

Syllabus

A Simple (1−eps)-Approximation Adaptive Sketching Algorithm for Maximum (Weighted) Matching

Taught by

Simons Institute

Reviews

Start your review of A Simple -Approximation Adaptive Sketching Algorithm for Maximum Weighted Matching

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.