Online Algorithms



  • 2019 Spring/Summer (Jan - May)

The course is targeted at graduate students
looking for an easy and rigorous introduction to online algorithms,
and hands on experience in solving real-world research problems. The
book first explores the canonical online problems, such as ski-rental,
caching, load balancing, secretary problem, knapsack problem, and
the set cover problem, etc.. Using this theoretical background, we
then consider some of the state-of-the- art online problems that are
relevant to many inter-disciplinary areas, and present multiple ideas to
work towards their solutions. The course is accessible to anyone with a
preliminary/very basic background in combinatorics, and probability,
together with mathematical maturity.
– Online Algorithms - Real World Examples
– Competitive Ratio
– Deterministic v/s Randomized
– Types of Adversaries
– Secretarial Input
– Ski-Rental Problem
– Introduction
– Deterministic Algorithms
– Randomized Algorithms
– Generalizations
– Paging Problem
– Introduction
– Deterministic Algorithms
– Randomized Algorithms
– Markov Input Model
– Multiple Caches
– Secretary Problem
– Introduction
– Real World Applications
– Sample and Price Algorithm
– Multiple Secretary Selection
– Knapsack Problem
– Introduction
– Randomized Algorithm
– Deterministic Algorithm with Large Market Assumption
– Matching
– Introduction
– Unweighted Maximum Weight Matching
– Weighted Maximum Weight Matching
– Budgeted Matching/ Adwords
– Introduction
– Unweighted Maximum Weight Matching
– Primal-Dual Algorithms
– Weighted Maximum Weight Matching

– Weighted Maximum Weight Matching with Hard Capacity Con-

– Set Cover
– Introduction
– Primal Dual Algorithm
– Disjoint Set Cover Problem

– Load Balancing
– Introduction
– General Case - Unrelated Machines
– Routing Algorithm
– Applications
References We will follow several lecture notes and research papers.
Book : Online Computation and Competitive Analysis, Borodin and
Course Project:
• A team of two students will be assigned a single semester-long research
project. The project’s purpose is help you build expertise in an area
related to applications of online algorithms to the point of being able to
contribute original research. The area of your project will be chosen
by you, with instructor guidance. The project has four main goals:
1) to build your background knowledge by having you read 6 papers
in your chosen area 2) to learn writing skills/techniques by writing
a summary of the 6 papers 3) to learn speaking skills/techniques by
presenting your area to the class 4) to push you to think about original
contributions to the area by working on extensions of the material you
• Course Project Meeting: Each team will meet with the instructor once
every week for an hour.
• You will read 6 research papers in the area. The papers you select are
also subject to instructor approval and guidance.
Grading: There will be 1 mid-term test with weightage of 20%. The course
project will be worth 40% of your grade. The rest 40% will comprise of
homeworks, and class performance.
Auditing Policy: Students planning to audit the course will be required
to turn in all the homeworks, exams, and the course project.