CS60023 Approximation and Online Algorithms

Instructor:

Sudeshna Kolay and Palash Dey

Teaching Assistants:

Aryan Sanghi

Course overview:

Many combinatorial and geometric optimization problems that arise in real-world applications are known to be NP-hard. According to computational complexity theory, designing efficient algorithms that compute exact optimal solutions for such problems is unlikely unless P = NP. Nevertheless, the need for efficient algorithms remains. A practical alternative is to relax the requirement of exact optimality and instead compute solutions that are provably close to the optimum within polynomial time. In many applications, such approximate solutions are sufficient, particularly when they can be obtained much more efficiently than exact ones. This motivates the study of approximation algorithms, which produce near-optimal solutions together with theoretical guarantees on their quality. These guarantees are expressed through the approximation ratio, which measures how close the computed solution is to the optimal one.

A related concept arises in the design of online algorithms, where decisions must be made without complete knowledge of the input. In many real-world scenarios, parts of the input become available only over time, requiring the algorithm to make irrevocable decisions based solely on the information seen so far. The performance of an online algorithm is evaluated using its competitive ratio, which compares its solution with that of an optimal offline algorithm that has access to the entire input in advance.

Classes:

Venue: CSE-302.

Timings: Monday 11-11:55 AM, Tuesday 8-9:55 AM.

Grading:

Attendance: 10%, Assignments: 10%, Class tests: 20%, Mid-term: 30%, Final: 30%

Announcements: Assignments:
Lectures:
Week 1
(SK)		 Introduction to Approximation Algorithms

Greedy Algorithms for Designing Approximation Algorithms:
Vertex Cover, Set Cover
k-Center, Job Scheduling on Single Machine

(reference: WS book)
Week 2
(SK)		 Job Scheduling on Single Machine
Local Search for Approximation Algorithm:
Job Scheduling on Multiple Machines
1-Additive Approximation of Edge Coloring

Metric TSP

(reference: WS book)
Week 3
(PD)		 FPTAS of Knapsack
EPTAS for Job Scheduling

(reference: WS book)
Week 4
(PD)		 APTAS for Bin Packing

(reference: WS book)

First Class Test
Week 5
(PD)		 Deterministic Rounding:
Prize Collecting Steiner Tree
Uncapacitated Facility Location

(reference: WS book)
Week 5
(PD)		 Randomized Approximation Algorithms: CNF-SAT
Method of Conditional Expectation

Randomized Rounding:
CNF-SAT, Prize Collecting Steiner Tree

(reference: WS book)


References:
  1. The Design of Approximation Algorithm by David P. Williamson David B. Shmoys. You can download free version here.
  2. Approximation Algorithms by Vijay V Vazirani. You can download free version here.
  3. Online Computation and Competitive Analysis by Allan Borodin and Ran El-Yaniv.