Speaker R. Ravi
Affiliation Tepper School of Business
Host Ravi Kannan
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.