Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Linear Programs and Deterministic Rounding

Speaker  R. Ravi

Affiliation  Tepper School of Business

Host  Ravi Kannan

Duration  01:32:07

Date recorded  20 December 2012

Linear and integer programs were introduced and simple deterministic rounding was demonstrated for the vertex cover problem (2-approximation). The homework assigned was to design a deterministic rounding algorithm for the prize-collecting vertex cover problem.

©2012 Microsoft Corporation. All rights reserved.
> Linear Programs and Deterministic Rounding