On-line and Approximation algorithms , Yossi Azar

On-line and Approximation Algorithms - 0368.4041

Yossi Azar ( azar@tau.ac.il )
1st Semester, 2011/12 - Wed 16-19, Schrieber 6
School of Computer Science,
Tel-Aviv University

Important: EXAM will take place on Wed, February 8, 2012

This page will be modified during the course, and will outline the classes.

Grade:

30% exercises
70% exam

Lecture notes template

noteTemplate.tex
noteTemplate.pdf

Lecture notes

Class-1 on 2.11.2011
Class-2 on 9.11.2011
Class-3 on 16.11.2011
Class-4 on 23.11.2011
Class-5 on 30.11.2011
Class-6 on 7.12.2011
Class-7 on 14.12.2011
Class-8 on 21.12.2011
Class-9 on 28.12.2011
Class-10 on 4.1.2012
Class-12 on 18.1.2012
Class-13 on 25.1.2012

For the outline of the course given in 2009/10 see course2009/10

Text books:

(1) Online computation and Competitive Analysis, A Borodin and R. El-Yaniv, Cambridge university press, 1998.
(2) Approximation Algorithms for NP-hard problems, edited by S. Hochbaum, PWS Publishing company, 1997.
(3) Online Algorithms - The State of the Art, edited by A. Fiat and G. Woeginger, Springer, 1998.
(4) Papers published in the last 25 years.
(5) Lecture notes from Brics 96 Susanne Albers

Course syllabus:

Online algorithms (algorithms that do not have all the information/input in advance) and some corresponding approximation algorithms.

Course outline

Nov 2, 2011 :
Introduction
Examples of approximations algorithms
2 approximation for vertex cover
Examples of on-line problems
Competitive ratio
Ski rental problem - 2 upper/lower bounds
Path searching problem - 9 upper/lower bounds
Machines Scheduling - 2 competitive
Nov 9, 2011 :
List update - definitions
List update - various algorithms
List update -2 competitive MF algorithm
List update - 2 lower bound
Nov 16, 2011 :
Paging - k competitive LRU/FIFO
Paging - k lower bound
k-server - k general lower bound
k-server on the line - k competitive Double Cover algorithm
Nov 23, 2011 :
Randomized algorithms
Quick sort, primality test, max cut
Ski rental - randomized upper/lower bounds
Survival game
Paging - 2H(k) competitive randomized marking algorithm
Nov 30, 2011 :
Paging - H(k) randomized lower bound
Oblivious, adaptive on-line and off-line adversaries
Relation between the adversaries
Load balancing - identical machines
Dec 7, 2011 :
Load balancing - related machines
Load balancing - restricted assignment - deterministic and randomized lower bound
Dec 14, 2011 :
Load balancing - restricted assignment - upper bound
Load balancing - unrelated machines
Virtual circuit routing
Dec 21, 2011 :
Benefit problems - financial problems - upper/lower bounds
Admission control and routing - general graphs
Dec 28, 2011 :
Admission control and routing - general graphs
Admission control on the line - lower bounds
Admission control on the line - classify & randomly select
Jan 4, 2012 :
Admission control on the line - preemptive algorithms
eight variants of admission control on the line:
Deterministic vs. randomized
Non-preemptive vs. preemptive
Jan 11, 2012 :
Value =1 vs. value = length
Scheduling problems - maximum completion time identical machines
Scheduling problems - reduction to batch
Response time (flow time) no release times - SPT
Jan 18, 2012:
Response time (flow time) with release times - SRPT
EDF for unit size unit value jobs
EDF for jobs of different size
Max value first for unit size jobs with arbitrary value
Jan 25, 2012:
Picking the winner
Exercises
Feb 1 , 2012:
Choice of two
Exercises