Coursera

Approximation Algorithms Part II (Coursera)

Offered by École normale supérieure,
Approximation Algorithms Part II (Coursera)

This is the continuation of Approximation algorithms, Part 1. Here you will learn linear programming duality applied to the design of some approximation algorithms, and semidefinite programming applied to Maxcut. By taking the two parts of 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.

Class Deals by MOOC List - Click here and see Coursera's Active Discounts, Deals, and Promo Codes.

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 second of a two-part course on Approximation Algorithms, this is the continuation of Approximation algorithms, Part 1

Syllabus

WEEK 1
Linear Programming Duality
This module does not study any specific combinatorial optimization problem. Instead, it introduces a central feature of linear programming, duality.

WEEK 2
Steiner Forest and Primal-Dual Approximation Algorithms
This module uses linear programming duality to design an algorithm for another basic problem, the Steiner forest problem.

WEEK 3
Facility Location and Primal-Dual Approximation Algorithms
This module continues teaching algorithmic applications of linear programming duality by applying it to another basic problem, the facility location problem.

WEEK 4
Maximum Cut and Semi-Definite Programming
We introduce a generalization of linear programming, semi-definite programming.This module uses semi-definite programming to design an approximation algorithm for another basic problem, the maximum cut problem.

Go to Class
MOOC List is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

Related Courses

Introduction to TCP/IP (Coursera) Coursera
Yonsei University

Introduction to TCP/IP (Coursera)

Security & Networking

You use the Internet through your PC (Personal Computer), laptop, tablet, smartpad, and smartphone every day in everything you do. Through your own PC/laptop, you can easily learn everything about the Internet, and that is what this course is focused on. In this course ‘Introduction to TCP/IP,’ you will learn the operational functions of Internet technologies (which include IPv4, IPv6, TCP, UDP, addressing, routing, domain names, etc.) and your PC/laptop's security and gateway Internet setup and basic principles.

Nov 9th 2026
5-12 Weeks
Internet TCP/IP Computer Science
Details
Operations Research (3): Theory (Coursera) Coursera
National Taiwan University

Operations Research (3): Theory (Coursera)

Computer Science

Operations Research (OR) is a field in which people use mathematical and engineering methods to study optimization problems in Business and Management, Economics, Computer Science, Civil Engineering, Electrical Engineering, etc. The series of courses consists of three parts, we focus on deterministic optimization techniques, which is a major part of the field of OR. As the third part of the series, we study mathematical properties of linear programs, integer programs, and nonlinear programs.

Nov 16th 2026
5-12 Weeks
Linear Programming Business Analytics Network Flow
Details
Problem Solving Using Computational Thinking (Coursera) Coursera
University of Michigan

Problem Solving Using Computational Thinking (Coursera)

CS: Theory Computer Science

Have you ever heard that computers "think"? Believe it or not, computers really do not think. Instead, they do exactly what we tell them to do. Programming is, "telling the computer what to do and how to do it." Before you can think about programming a computer, you need to work out exactly what it is you want to tell the computer to do. Thinking through problems this way is Computational Thinking. Computational Thinking allows us to take complex problems, understand what the problem is, and develop solutions. We can present these solutions in a way that both computers and people can understand.

Nov 9th 2026
5-12 Weeks
Programming Algorithms Computational Thinking
Details
An Introduction to Cryptography (Coursera) Coursera
University of Leeds

An Introduction to Cryptography (Coursera)

Computer Science

Cryptography is an essential part of secure but accessible communication that's critical for our everyday life and organisations use it to protect their privacy and keep their conversations and data confidential. This course provides a comprehensive introduction to the fascinating world of cryptography, covering both historical cyphers and modern-day cryptographic techniques.

Nov 16th 2026
2 Weeks
Cryptography Algorithms Encryption
Details
Approximation Algorithms (Coursera) Coursera
EIT Digital

Approximation Algorithms (Coursera)

Computer Science

Many real-world algorithmic problems cannot be solved efficiently using traditional algorithmic tools, for example because the problems are NP-hard. The goal of this course is to become familiar with important algorithmic concepts and techniques needed to effectively deal with such problems. These techniques apply when we don't require the optimal solution to certain problems, but an approximation that is close to the optimal solution. We will see how to efficiently find such approximations.

Nov 13th 2026
4 Weeks
Algorithms Approximation Algorithms LP Relaxation
Details
Internet History, Technology, and Security (Coursera) Coursera
University of Michigan

Internet History, Technology, and Security (Coursera)

Security & Networking

The impact of technology and networks on our lives, culture, and society continues to increase. The very fact that you can take this course from anywhere in the world requires a technological infrastructure that was designed, engineered, and built over the past sixty years. To function in an information-centric world, we need to understand the workings of network technology. This course will open up the Internet and show you how it was created, who created it and how it works. Along the way we will meet many of the innovators who developed the Internet and Web technologies that we use today.

Nov 16th 2026
5-12 Weeks
Network Security Computing
Details
Digital Signal Processing 1: Basic Concepts and Algorithms (Coursera) Coursera
École Polytechnique Fédérale de Lausanne

Digital Signal Processing 1: Basic Concepts and Algorithms (Coursera)

Engineering

Digital Signal Processing is the branch of engineering that, in the space of just a few decades, has enabled unprecedented levels of interpersonal communication and of on-demand entertainment. By reworking the principles of electronics, telecommunication and computer science into a unifying paradigm, DSP is a the heart of the digital revolution that brought us CDs, DVDs, MP3 players, mobile phones and countless other devices.

Nov 9th 2026
4 Weeks
Algorithms Electrical Engineering Fourier Transform
Details
Algorithmic Thinking (Part 1) (Coursera) Coursera
Rice University

Algorithmic Thinking (Part 1) (Coursera)

CS: Theory

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 train students in the mathematical concepts and process of "Algorithmic Thinking", allowing them to build simpler, more efficient solutions to computational problems.

Nov 2nd 2026
4 Weeks
Python Computing Algorithms
Details
Securing Digital Democracy (Coursera) Coursera
University of Michigan

Securing Digital Democracy (Coursera)

Security & Networking

In this course, you'll learn what every citizen should know about the security risks--and future potential — of electronic voting and Internet voting. We'll take a look at the past, present, and future of election technologies and explore the various spaces intersected by voting, including computer security, human factors, public policy, and more.

Nov 16th 2026
5-12 Weeks
Digital Security Operating Systems
Details