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
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
Category
📚
Éducation