Chevron Left
返回到 Approximation Algorithms Part I

Approximation Algorithms Part I, 法国巴黎高等师范学院

(123 个评分)


Approximation algorithms, Part I How efficiently can you pack objects into a minimum number of boxes? How well can you cluster nodes so as to cheaply separate a network into components around a few centers? These are examples of NP-hard combinatorial optimization problems. It is most likely impossible to solve such problems efficiently, so our aim is to give an approximate solution that can be computed in polynomial time and that at the same time has provable guarantees on its cost relative to the optimum. This course assumes knowledge of a standard undergraduate Algorithms course, and particularly emphasizes algorithms that can be designed using linear programming, a favorite and amazingly successful technique in this area. By taking this course, you will be exposed to a range of problems at the foundations of theoretical computer science, and to powerful design and analysis techniques. Upon completion, you will be able to recognize, when faced with a new combinatorial optimization problem, whether it is close to one of a few known basic problems, and will be able to design linear programming relaxations and use randomized rounding to attempt to solve your own problem. The course content and in particular the homework is of a theoretical nature without any programming assignments. This is the first of a two-part course on Approximation Algorithms....


创建者 DA

Jan 27, 2016

The course provides a high-level introduction to approximation algorithm. There is no programming assignments but it provides nice introduction to approximation algorithm.

创建者 ZW

Sep 17, 2017

This course is awesome. Prof. managed to elaborate the problem and analysis clearly and homework is properly assigned.


33 个审阅

创建者 Anupam Gupta

Oct 19, 2017

I am a researcher and (in past) an instructor in SDP, Randomized and Approximation Algorithms.

There are a few instances, where things are not explained as well as an advanced UG or a starting Grad student would like, e.g., Knapsack got a bit delirious somewhere in between (the "special special" case, which IMHO was not needed.)

Otherwise, I love Claire's enthusiasm, and the joy she finds in delivering the ideas. She is succinct everywhere (to me).

创建者 Roberto Pereira Garcia Junior

Sep 21, 2017

Very good !

创建者 Zitong Wang

Sep 17, 2017

This course is awesome. Prof. managed to elaborate the problem and analysis clearly and homework is properly assigned.

创建者 Antonio Cruciani

Jul 27, 2017

Really good course and Professor.

创建者 victor guillot

Jul 21, 2017

A very synthetic course on the topic.Explanations are of great quality and elegant!

Every algorithms given are analysed on a mathematical point of view.

ENS should enable people to get certificate for this course ! I would prefer

give money to this top institution in theorical science than to the huge private universities

To improve : the commitment of the staff to the forum

创建者 Peter Unold

Jun 01, 2017

The content of the course is good and the lectures even better. However the quizzes and homeworks could use an update or refresh. The forums connected to the course is a ghosttown.

创建者 Pasquale De Meo

May 30, 2017

super cool!

创建者 Paulo Emílio de Vilhena

Feb 13, 2017

Great course!

创建者 Zhouningnan

Jan 11, 2017

This class is very clear and easy to understand! Thank you for providing such feast for students!

创建者 Susanne Wienand

Jan 09, 2017