**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

Avrim Blum Last modified: Tue Jan 18 16:28:18 EST 2000