## Advanced Heuristic and Approximation AlgorithmsThis course will focus on algorithms and heuristics for discrete optimization problems. We will study algorithmic techniques based on combinatorial and spectral methods as well as approaches based on rounding mathematical programming formulations of discrete optimization problems. We will also study efficient algorithms for solving such relaxations. The main areas of application will be graph partitioning (e.g. minimum cut and maximum cut), graph traversal (e.g. Chinese postman problem and traveling salesman problem), randomized LP rounding (e.g. set cover and maximum satisfiability). We may also study graph decomposition (e.g. small set expansion). ## (Tentative) Course Topics## Graph Partitioning:Karger's Algorithm for Minimum Cut Goemans-Williamson Algorithm for Maximum Cut and Maximum-k-Cut Spectral Partitioning; Cheeger Inequality ## Graph Traversal:Traveling Salesman Problem Chinese Postman Problem Asymmetric Traveling Salesman Problem ## Randomized LP Rounding:Maximum Satisfiability Set Cover Dominating Set in Digraphs ## Time Permitting:Arora-Barak-Steurer Algorithm for Small-Set Expansion/Unique Games Arora-Rao-Vazirani Algorithm for Sparsest Cut |

Last modified on September 07, 2018, at 12:46 PM