M2 Course Proposal: Algorithms and Heuristics for Optimization and Approximation

• Instructors: Alantha Newman and ??

• Prerequisites: Basic concepts in algorithms, complexity theory, linear algebra and discrete probability.

• Objective: Approximation algorithms is a widely studied research area in which the goal is to design efficient algorithms with provable guarantees for NP-hard optimization problems. The objective of this course is to study classic and foundational techniques and approaches developed in this research area, as well as to gain familiarity with some recent advances in the field. Topics will include algorithms for linear/convex programming, extracting integer solutions from optimal fractional solutions using tools such as randomized and iterative rounding, and algorithms for classic NP-hard optimzation problems such as the traveling salesman problem.

• Course Outline:
  
  1) Obtaining optimal (fractional) solutions for relaxations.
  

  • This part will cover approaches to solve linear and convex programs efficiently or fast in practice. Such programs can be viewed as relaxations of discrete optimization problems that are hard to solve in general.
  • This part could include modern methods for solving linear programs such as adaptations of the Ellipsoid algorithm and multiplicative weights. It might also contain some work on aspects of the Simplex algorithm in terms of provable efficiency and practical performance. (Note: This depends on the other lecturers; see notes below.)
  
  2) Obtaining near-optimal integral solutions.
  
  
  • This part will cover classic approaches for "rounding" fractional solutions for convex programs to obtain provably near-optimal integer solutions. We will cover classic tools such as randomized and iterative rounding of linear programs, primal-dual algorithms, random-hyperplane rounding for semidefinite programs, and recent techniques using LP hierarchies. In some cases, we consider more problem-specific rounding approaches, based on extreme point structure or on other ways of extracting structure from fractional solutions.
  • Some examples of optimization problems we will study are: min and max-cut, clustering and graph partitioning, scheduling, coloring, unique games, traveling salesman problem.

• Evaluation: There will be a written final exam and either a homework assignment or an oral presentation of a research article.

• Related Resources:
  
  

  1. The Design of Approximation Algorithms by David P. Williamson and David B. Shmoys
     
  2. Graph Partitioning, Expanders and Spectral Methods by Luca Trevisan at UC Berkeley
  3. Approximation Algorithms Traveling Salesman Problems by Vera Traub and Jens Vygen at Universitaet Bonn

• Notes: Sophie Huiberts from LIMOS said she might be interested in co-teaching, in which case she would focus on recent developments around the Simplex algorithm (e.g., smoothed analysis, practical performance). She said it is too far in advance to commit. I would prefer to find someone else with whom to co-teach and I am currently still looking for someone. This might entail altering the course proposal a bit, but approximation algorithms/efficient algorithms related to optimization will be the main topic of the course.