Back to Approximation Algorithms Part I

4.7

stars

132 ratings

•

37 reviews

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.

MH

May 29, 2020

A great course if you want to learn about approximation algorithms from the point of view of linear programming relaxation!

Filter by:

By Mika M

•Jan 23, 2016

The course deals not with programming, but rather with designing and analyzing approximation algorithms. The course is on a high level and focuses on the subject without too much side remarks on applications, connections to other subjects or motivational introductions. If you are a theory person, however, you will probably enjoyed it.

By D. a

•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.

By Mustafa Q

•Jan 03, 2017

I love how this course delves into a very promising advanced research topic in Computational Complexity. It helps me a lot to understand trending publications in the area. Specially that the material is presented in an incremental approach. This way a researcher can live through the evolution of ideas. It is inspiring also in the way one comes up with a partial solution for the special case, and then generalizes with approximation factor that is satisfyingly good. I'm looking forward to more advanced courses in parameterized, streaming or quantum algorithms.

By Anupam G

•Feb 19, 2020

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).

By Ilya T

•Aug 27, 2016

The assignments could be a bit improved (some are less good, I would personally complain about knapsack), but in general it is a great course, as it gives an accessible introduction to approximation algorithms (for NP-hard problems), which is a very relevant topic, as NP-hard problems are everywhere.

At the time of writing (end summer 2016), it is also a unique course for this very relevant topic.

By Pavel V

•Feb 08, 2016

Really good course, the material is quite advanced but very well structured and introduced in a very simple way. The assignments were a lot of fun: really enjoyed the peer-graded assignments where I needed to write short proofs, much more useful than regular multiple-choice answers. Looking forward to the next course!

By Jun Q

•Dec 05, 2015

This class is the one I am seeking for a long time. Theories of Combinatorial optimization and associated approximation algorithms involve lots of hot research topics in machine learning, image processing, and Bioinformatics. The faculty for this course is a leading expert in the related fields.

By Christophe C

•Jun 12, 2016

Excellent advanced course! Not for beginner in computer science, nor for people more interested in applying computer science than in theoretical foundations.

By Mursalin H

•May 29, 2020

A great course if you want to learn about approximation algorithms from the point of view of linear programming relaxation!

By Zitong W

•Sep 17, 2017

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

By Swaprava N

•Jun 27, 2016

This was a relatively easy but well paced introduction to approximation algorithms. I totally enjoyed it.

By Nihal B

•Feb 05, 2016

A useful course which introduces key ideas in Approximation Algorithms. Looking forward to part II.

By Zhouningnan

•Jan 11, 2017

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

By Karthick S

•May 26, 2016

Excellent Course! I have learnt a lot about Approximation Algorithms in a short span of time.

By Obinna O

•Jan 16, 2016

awesome course!

I'd like to see part 2 and other graduate-level algorithms courses on coursera.

By Aliaksei K

•Apr 17, 2016

A really good course for programmers who want to take a bit deeper into CS.

By Do H L

•Jan 21, 2016

Very high-level course. After week1 and I'm already excited to start it

By Joel K

•May 22, 2016

Great class, and Professor Claire Mathieu is doing an excellent job!

By Deleted A

•Dec 27, 2015

very nice course. i look forward to the second part!

By Emanuel M

•Nov 06, 2016

good course, with many examples and explanations

By Eoin M

•May 18, 2020

Fantastic course! Can't wait to do part ii

By Antonio C

•Jul 27, 2017

Really good course and Professor.

By Zhenwei L

•Aug 16, 2019

I love this course!

By Paulo E d V

•Feb 13, 2017

Great course!

By Roberto p g j

•Sep 21, 2017

Very good !

- Finding Purpose & Meaning in Life
- Understanding Medical Research
- Japanese for Beginners
- Introduction to Cloud Computing
- Foundations of Mindfulness
- Fundamentals of Finance
- Machine Learning
- Machine Learning Using Sas Viya
- The Science of Well Being
- Covid-19 Contact Tracing
- AI for Everyone
- Financial Markets
- Introduction to Psychology
- Getting Started with AWS
- International Marketing
- C++
- Predictive Analytics & Data Mining
- UCSD Learning How to Learn
- Michigan Programming for Everybody
- JHU R Programming
- Google CBRS CPI Training

- Natural Language Processing (NLP)
- AI for Medicine
- Good with Words: Writing & Editing
- Infections Disease Modeling
- The Pronounciation of American English
- Software Testing Automation
- Deep Learning
- Python for Everybody
- Data Science
- Business Foundations
- Excel Skills for Business
- Data Science with Python
- Finance for Everyone
- Communication Skills for Engineers
- Sales Training
- Career Brand Management
- Wharton Business Analytics
- Penn Positive Psychology
- Washington Machine Learning
- CalArts Graphic Design

- Professional Certificates
- MasterTrack Certificates
- Google IT Support
- IBM Data Science
- Google Cloud Data Engineering
- IBM Applied AI
- Google Cloud Architecture
- IBM Cybersecurity Analyst
- Google IT Automation with Python
- IBM z/OS Mainframe Practitioner
- UCI Applied Project Management
- Instructional Design Certificate
- Construction Engineering and Management Certificate
- Big Data Certificate
- Machine Learning for Analytics Certificate
- Innovation Management & Entrepreneurship Certificate
- Sustainabaility and Development Certificate
- Social Work Certificate
- AI and Machine Learning Certificate
- Spatial Data Analysis and Visualization Certificate

- Computer Science Degrees
- Business Degrees
- Public Health Degrees
- Data Science Degrees
- Bachelor's Degrees
- Bachelor of Computer Science
- MS Electrical Engineering
- Bachelor Completion Degree
- MS Management
- MS Computer Science
- MPH
- Accounting Master's Degree
- MCIT
- MBA Online
- Master of Applied Data Science
- Global MBA
- Master's of Innovation & Entrepreneurship
- MCS Data Science
- Master's in Computer Science
- Master's in Public Health