[2016 MPRI 2.11.1] 4. Polynomial Time Approximation Schemes (2016/10/5)

MPRI - Parisian Master of Research in Computer Science
Course 2.11.1: Approximation Algorithms, Randomization & Nature Programming
Nicolas SCHABANEL, CNRS - Université Paris Diderot

LECTURE 4 (2016/10/5)
POLYNOMIAL-TIME APPROXIMATION SCHEMES

[0:00:00] 0. (F)PT(R)AS: (Fully) Polynomial-Time (Randomized) Approximation Schemes
[0:10:31] 1. A FPTAS for the Knapsack Problem
[1:05:27] 2. A FPTRAS for Max-Cut in α-Dense Graphs