Lectures:MW 1:30-2:50, Wean 4615A.
Office hours:MW 3:00-3:30 (i.e., after class)
Course Description: This course explores the two related topics of Approximation Algorithms and Online Algorithms. Both of these involve the goal of finding provably good approximate solutions to problems that are hard to solve exactly. In the case of approximation algorithms, the difficulty is overcoming computational intractibility; in the case of online algorithms, the difficulty is a lack of full information about the input. Algorithms for both of these situations involve a collection of interesting techniques such as randomized rounding, semidefinite programming, and potential-function approaches. We will explore a variety of problems within these areas as well as connections to other areas such as online machine learning.
Admin: Grading will be based on a collection of homework assignments, a take-home final, and class participation. As part of class participation, each student (possibly in teams) will give a class presentation on a topic chosen in consultation with the instructor. Because this course has no TA, students from time to time will also be asked to help with the grading of assignments.
Readings: There is no required textbook. Instead, a collection of survey papers, lecture notes, and research papers will be made available on the course webpage and/or handed out in class. For the Online Algorithms portion of the course, a recommended (but not required) text is Online Computation and Competitive Analysis by Allan Borodin and Ran El-Yaniv.
Schedule: Roughly, we will begin with Approximation Algorithms, then move on to Online Algorithms, and then discuss topics in common to both. Below is a list of topics I would like to cover (but which may change without warning...)
Approximation Algorithms Methods: - greedy - (randomized) rounding of LP - Semi-definite Programming - primal-dual - conductance & expanders - Dynamic Programming approx - Metric space approximation and projection Problems: - Vertex-cover, set-cover - TSP and related problems - routing - MAX-SAT - Comp bio: e.g., shortest superstrings - MAX-Cut - graph coloring - graph separators - subgraph problems - geometric problems - counting/estimation problems Other: - approximation hardness. Online Algorithms: Methods: - potential functions - randomization - work function - exponential-weights - metric space approximation Problems: - Metrical Task System - paging - k-server - navigation problems - online learning - data structures: lists and trees - load balancing & scheduling - call control & routing - portfolio allocation