CS60023: Approximation and Online Algorithms

It is well-known that most combinatorial and geometric optimization problems arising out of real world scenarios turn out to be NP-hard. From computational complexity theory, we know that it is impossible to design efficient algorithms for solving such problems exactly unless P=NP, which is very unlikely to be the case. This does not obviate the need for designing efficient polynomial time algorithms for these problems. However, we may relax the stringent requirement of computing an exact optimal solution. In practice, it serves our purpose well enough if we can obtain a near optimal solution instead of an exact optimal, especially when the former can be computed much faster. This results in the notion of the “approximate” solution of an optimization problem. As a computer scientist and engineer, it is often worthwhile to focus on designing efficient algorithms that output an approximate solution, but at the same time provide a relative performance guarantee that the value of the solution is within some factor (this factor is called the “approximation ratio”) of the optimal value.

In the same spirit of approximation ratios, the performance of an online algorithm is measured in terms of “competitive ratios”. Many algorithmic problems that arise in practice are of online nature. In these problems, the input is only partially available because some relevant input arrives only in future, and ia not available at the time of making certain decisions. An online algorithm must generate output without the knowledge of the entire input.

Approximation algorithms [27 hours]

1. Introduction and performance measures [1 hour]
2. Greedy Algorithms and Local Search: [13 hours]

   (a) graph algorithms [4 hrs] (b) job scheduling algorithms [2 hours] (c) set cover [1 hour] (d) combinatorial problems such as bin packing and knapsack etc. [4 hours] and (e) geometric problems [2 hours].

3. Rounding Data and Dynamic Programming: [4 hours] Approximation Schemes for knapsack, binpacking and scheduling problems.
4. Deterministic Rounding of Linear Programs: [5 hours] Scheduling, facility location and optimization problems such as bin packing.
5. The Primal-dual Method: [4 hours] Set cover, vertex cover and weighted vertex cover, etc.

Online algorithms [13 hours]

1. Competitive analysis of online algorithms [1 hour]
2. The Paging Problem [1 hour]
3. Amortized analysis of online algorithms [1+1/2 hour]
4. The List Update Problem [1 hour]
5. Problem of searching for a target in a bounded or unbounded region. [2+1/2 hours]
6. Online graph coloring [2 hours]
7. The K-server problem [2 hours]
8. Online scheduling algorithms [2 hours]