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

YouTube

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

Simons Institute via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore a 39-minute lecture on approximating k-edge-connected spanning subgraphs (kECSS) using a near-linear time LP solver. Delve into the NP-hard problem of computing minimum-cost sub-networks resilient against up to k link failures. Learn about the improved algorithm that achieves a (1+ε)-approximation of the optimal fractional solution in Õ(m/ε²) time, independent of k. Discover how this can be transformed into a (2+ε) approximation algorithm for integral kECSS, running in Õ(m/(ε²) + {k²n^{1.5}}/ε²) time. Compare this advancement to previous results, noting the improved running time while maintaining an approximation ratio close to two. Gain insights into the broader class of survival network design problems (SNDP) and their applications in optimization and algorithm design.

Syllabus

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

Taught by

Simons Institute

Reviews

Start your review of Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

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.