Reading Group Algorithms: Continuous Methods for Combinatorial Problems

In the recent years, algorithms for convex optimization have revolutionized the design of algorithms, both for discrete as well as continuous optimization problems. At present, the fastest known algorithms for problems such as maximum flow in graphs, maximum matching in bipartite graphs, and submodular function minimization involve the use of algorithms for convex optimization like the gradient descent, mirror descent, interior point methods, and cutting plane methods. The goal of this course is to gain an understanding of the algorithms for convex optimization and see how they find applications in solving combinatorial optimization problems.

In this seminar course, we read the book Algorithms for Convex Optimization by Nisheeth Vishnoi. This is the most contemporary book in the area. The instructors will present the introductory chapters of the book (Chapter 2,3,4) in the first few weeks of the course. Every lecture of the subsequent week will consist of 2-3 student presentations. Each week (after the introductory chapters are covered), all the students are expected to prepare roughly one chapter of the book. The contents of the chapter would be divided into 2-3 logical parts, each forming one individual presentation. The decision on who presents in the coming lecture will be based on a random choice that will be made just before the lecture begins. Thus, every student is expected to be prepared with one chapter of the book every week. A student can refuse to make the presentation, after the random decision is made, at most twice throughout the course. An absence from the lecture counts as one refusal. Note that if the course is conducted non-virtually then the presentations could be made on the blackboard/whiteboard. At the end of the course, a student may or may not submit a written summary of one of the important chapters in the book. Submitting a summary is optional and can lead to an increase or decrease in the grade depending on its quality.

If you have any doubts while preparing for your presentations, you can reach out to one of the instructors well in advance before the day of presentation. The reading group counts as a seminar in your study program. You can register by sending an e-mail to Roohani. Please make sure that you read the section on prerequisites above before you register.

Algorithms for Convex Optimization by Nisheeth Vishnoi.