Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Filtering and the Primal-Dual Method - Part 1

Speaker  R. Ravi

Affiliation  Tepper School of Business

Host  Ravi Kannan

Duration  01:03:44

Date recorded  21 December 2012

Two LP-based methods were covered. Filtering the optimal LP solution was illustrated to design a constant factor approximation for the metric uncapacitated facility location problem. The primal-dual method was illustrated by designing a 2-approximation algorithm for the generalized Steiner forest problem.

©2012 Microsoft Corporation. All rights reserved.
> Filtering and the Primal-Dual Method - Part 1