Online Algorithms

Course Objectives: 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.

Syllabus: – 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 Constraint – 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 El-Yaniv.

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 learn.

• Course Project Meeting: Each team will meet with the insturctor 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.