COSC 49.06 Approximation Algorithms

Many problems arising in computer science are NP-hard and therefore we do not expect polynomial time algorithms solving them exactly. This has led to the study of approximation algorithms where one relaxes the goal to return approximate solutions. Over the past three decades, a beautiful theory of approximation algorithms has emerged. This course will provide a broad overview of the main techniques and will often deep dive into the state-of-the-art.

Prerequisite

COSC 31

Degree Requirement Attributes

Dist:QDS

The Timetable of Class Meetings contains the most up-to-date information about a course. It includes not only the meeting time and instructor, but also its official distributive and/or world culture designation. This information supersedes any information you may see elsewhere, to include what may appear in this ORC/Catalog or on a department/program website. Note that course attributes may change term to term therefore those in effect are those (only) during the term in which you enroll in the course.