Curriculum

  /  

Descriptions

COMP_SCI 496: Advanced Topics in Approximation Algorithms

VIEW ALL COURSE TIMES AND SESSIONS

Prerequisites

COMP_SCI 437 or instructor approval

Description

This is a second course on approximation algorithms that focuses on more advanced topics in the field. Below is a tentative list of topics to be covered:

1. Semidefinite Programming (SDP): Includes the Goemans-Williamson algorithm for MAX-CUT, the Karger-Motwani-Sudan algorithm for 3-Coloring, the Arora-Rao-Vazirani algorithm for Balanced Cut, the Raghavendra-Steurer algorithm for MAX CSPs, Cheeger's inequality, and some inapproximability results.

2. Metric Embeddings and Dimension Reduction: Applications to approximation algorithms, including Bourgain's Theorem, embedding into a distribution of trees, Räcke's hierarchical decomposition, and the Johnson–Lindenstrauss transform.

3. Brief Introduction to Sherali-Adams Relaxation and Sum of Squares (SoS): Includes the Raghavendra-Tan algorithm for Max Bisection.

4. Advanced Algorithms for Classic Optimization Problems: Topics such as Facility Location and Group Steiner Tree.

RECOMMENDED TEXTS:

• Approximation Algorithms by Vijay Vazirani.
• The Design of Approximation Algorithms by David Williamson and David Shmoys. A copy of this book is available online (http://www.designofapproxalgs.com/book.pdf).

COURSE INSTRUCTOR: Prof. Konstantin Makarychev