Approximation Algorithms Part I

Description

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.

Subsections



More Ways to Learn Algorithms

Algorithms

High School - College | Online class

We’ve partnered with Dartmouth college professors Tom Cormen and Devin Balkcom to teach introductory computer science algorithms, including searching, sorting, recursion, and graph theory. Learn...

Free

Algorithmic Toolbox

College | Online class

Algorithmic Toolbox is course 1 of 6 in the Data Structures and Algorithms Specialization. The Specialization covers algorithmic techniques for solving problems arising in computer science...

Free
Offers paid add-ons

Approximation Algorithms Part II

College | Online class

Approximation algorithms, Part 2 This is the continuation of Approximation algorithms, Part 1. Here you will learn linear programming duality applied to the design of some approximation algorithms,...

Free

Introduction to Recommender Systems

College | Online class

Recommender systems have changed the way people find products, information, and even other people. They study patterns of behavior to know what someone will prefer from among a collection of things...

Free

Master Algorithmic Programming Techniques

College | Online class

The Specialization covers algorithmic techniques for solving problems arising in computer science applications. It is a mix of theory and practice: you will not only design algorithms and estimate...

$79

Advanced Algorithms and Complexity

College | Online class

You’ve learned the basic algorithms now and are ready to step into the area of more complex problems and algorithms to solve them. Advanced algorithms build upon basic ones and use new ideas. We...

Free

Algorithms on Strings

College | Online class

World and internet is full of textual information. We search for information using textual queries, we read websites, books, e-mails. All those are strings from the point of view of computer...

Free

Algorithm Master: Python

7th - College | Online class

This course guides students through learning Python, with an emphasis on algorithms and data structures. This track covers recursion, searching algorithms, sorting algorithms, big-O notation, and...

$250 monthly
Offers paid add-ons

Algorithmic Thinking (Part 2)

7th - College | Online class

Experienced Computer Scientists analyze and solve computational problems at a level of abstraction that is beyond that of any particular programming language. This two-part class is designed to...

Free
Offers paid add-ons

CS303: Algorithms

College | Online class

This course focuses on the fundamentals of computer algorithms, emphasizing methods useful in practice. We look into the algorithm analysis as a way to understand behavior of computer programs as a...

Free

See all resources for Algorithms