ReePrime
Blog DMC
[MPRI 2012] Approximation Algorithms 2B

Hosted by Dailymotion. For legal issues report at the Copyright Center, report us on DMC, or use the Instant Removal tool.

[MPRI 2012] Approximation Algorithms 2B

N
Nicolas Schabanel

1 Views • Oct 06, 2012

Description

Lecture on Approximation Algorithms at the Parisian Computer Science Master
by Nicolas Schabanel
[ Session 2 Part B/B ]

Lecture 2: Wed Oct 3, 2012 - 12:45-15:45

Linear Programming
Introduction, LP Relaxation, First rounding (Vertex-Cover)
Duality and Complementary Slackness Conditions
Application: primal-dual algorithm for Vertex-Cover & Maximum/-al Matching
(Note for next year: primal dual algorithm for Set-Cover would have been a better choice)

Keywords & Tags

#computer science #theory of computing #algorithms #approximation #linear programming

More from User

02:46:55

[2017 MPRI 2.11.1] Molecular programming 3/4 (8 NOV)

Nicolas Schabanel

02:14:45

[2017 MPRI 2.11.1] Molecular programming 4/4 (15 NOV)

Nicolas Schabanel

02:39:19

[2017 MPRI 2.11.1] Molecular programming 2/4 (25 OCT)

Nicolas Schabanel

02:28:07

[2017 MPRI 2.11.1] Molecular programming 1:4 (18 OCT)

Nicolas Schabanel

02:30:29

[2016 MPRI 2.11.1] 7. Nature Programming: Intrisic Universality & Other models including Oritatami (2016/11/9)

Nicolas Schabanel

02:49:34

[2016 MPRI 2.11.1] 6. Nature Programming: Universality in Tile Assembly Systems (2016/11/2)

Nicolas Schabanel

Related Videos

01:00:00

[MPRI 2012] Approximation Algorithms 3B

Nicolas Schabanel

02:54:45

[2016 MPRI 2.11.1] 1. Introduction to Approximation Algorithms (2016/9/14)

Nicolas Schabanel

01:00:50

[MPRI 2012] Approximation Algorithms 4C

Nicolas Schabanel

01:00:04

[MPRI 2012] Approximation Algorithms 1A

Nicolas Schabanel

01:00:00

[MPRI 2012] Approximation Algorithms 3A

Nicolas Schabanel

01:00:00

[MPRI 2012] Approximation Algorithms 2A

Nicolas Schabanel