NYU Approximation Algorithms

Instructor: Anupam Gupta

Lecture: Thursdays at 2:45-4:45pm ET, 202 Warren Weaver

(We plan to extend the lecture until 5:15, so that we do not have to rush. If that is a problem for you, please contact the instructor before registering!)

Course Numbers: CSCI-GA.3033-138

Professors office hours: TBA/By appointment.

Overview: This is a graduate course in the design and analysis of approximation algorithms. Many discrete optimization problems are known to be NP-hard and hence are unlikely to admit efficient (polynomial time) algorithms. One approach around this intractability is to develop polynomial-time algorithms that find solutions with objective value close to optimal; these are known as approximation algorithms. Over the years, many techniques such as linear and convex programming, use of randomness, and metric embeddings, have been developed to design/analyze the quality of these algorithms. Along with these algorithmic approaches, techniques have been developed to show inapproximability, i.e., to show limits to how well problems can be approximated using some restricted set of techniques, or assuming conjectures like P\neq NP, or the Unique Games Conjecture. The aim of the course is to expose students to ideas from both these threads of research.

Time permitting, we will also discuss online algorithms/sequential decision making, where the input is revealed over time, but now decisions have to be made over time, as the input is being revealed. Using some of the techniques developed above (plus some new ones), we will give algorithms and matching lower bounds for these online settings.

The focus of this course is to present both the algorithmic ideas, and the ideas behind their analysis, so we expect the students to have mathematical maturity and strong problem-solving abilities. A detailed syllabus will be posted as the course progresses.

Prerequisites: We expect students to have a good background in algorithm design. For example, Honors Analysis of Algorithms (CSCI-GA.3520-001), Algorithms 2 (CS-GY 6043), Algorithmic Machine Learning and Data Science (CS-GY 6763), or similar graduate-level Algorithms courses. Solid understanding of probability, linear algebra, and calculus, and mathematical maturity is a must.

Enrollment: If you are an NYU student wishing to enroll for the course and need permission, please remember to send me a CV and a current transcript, and give some background on your preparation for the course.

Grading breakdown: The course evaluation will be based on 3-4 homework sets, and some in-class exams TBD. Depending on the class size, some of the homeworks may be oral homeworks. We anticipate that much of the weight will be on the in-person components.

GenAI Policy: You are allowed (and encouraged) to use Generative AI to learn the materials. However, their use is at your own risk: indiscriminate use will mean that you don't learn how to solve problems, which may adversarially affect your performance in the in-person evaluations. We may also use GenAI in the evaluation process, e.g., to give you feedback on your homework submissions, and to evaluate you. This is a rapidly evolving area, and we will update you with the latest details.

Course Infrastructure: We will use Ed for course discussions, Gradescope for homework submissions, and Brightspace for all course material. In addition, we will post as much material here as possible.

Collaboration: For some of the problems, we will ask you to work solo, whereas for others we will allow collaboration in small groups. Each person must write their own solutions to submit.

Resources: There is no official textbook. We like these books:
The Design of Approx. Algorithms by David Williamson and David Shmoys
Approximation Algorithms by Vijay Vazirani.
(Other books/materials to come soon.)

We will post readings from books and research papers, which will be available free online or via the NYU library.

Homeworks: