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

YouTube

Approximation Algorithms

Association for Computing Machinery (ACM) via YouTube

Overview

Explore approximation algorithms in this 41-minute ACM conference talk. Dive into the Connectivity Augmentation Problem and its reduction to Steiner Tree. Examine lower bounds and approximation algorithms using linear programming. Investigate spectral network design, including generalized survivable networks and spectral rounding. Learn about main results, spectral certificates, and future work in the field. Conclude with insights into conjunctive normal form (CNF) and classic Glauber dynamics Gibbs sampling.

Syllabus

Intro
Connectivity Augmentation Problem
Reduction to Steiner Tree
Reduction from CAP to Steiner Tree
Lower Bound
Obtaining Approximation Algorithm
Linear Programming
Motivation for Spectral Network Design
Generalized Survivable Network Design
Spectral Rounding
First Main Result
Second Result
Spectral certificate
Future Work
Conjunctive normal form (CNF)
Classic Glauber dynamics Gibbs sampli

Taught by

Association for Computing Machinery (ACM)

Reviews

Start your review of Approximation Algorithms

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.