On-line and
Approximation Algorithms - 0368.4041
Yossi Azar (
azar@tau.ac.il )
2nd Semester, 2023/24 - Mon 16-19, Checkpoint 001
School of Computer Science,
Tel-Aviv University
EXAM is on Aug 28,
2024 at 9am
This page will be modified during the course.
Grade:
30% exercises
70% exam
NEW *** NEW *** NEW *** Examples of Exams
Exam 2013/14
Exam 2011/12
Exam 2009/10
Exam 2006
Exercises:
Exercise1 (Due on Jun 30, 2024)
Exercise2 (Due on Jul 21, 2024)
Exercise3 (Due on Aug 11, 2024)
Lecture notes
Class-1
Class-2
Class-3
Class-4
Class-5
Class-6
Class-7
Class-8
Class-9
Class-10
Class-11
Class-12
Class-13
For
the outline of the course given in 2021/22 see course2021/22
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
1.
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
2.
List
update - definitions
List update - various algorithms
List update -2 competitive MF algorithm
List update - 2 lower bound
3.
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
4.
Randomized
algorithms
Quick sort, primality test, max cut
Ski rental - randomized upper/lower bounds
Survival game
Paging - 2H(k) competitive randomized marking algorithm
5.
Paging - H(k) randomized lower bound
Oblivious, adaptive on-line and off-line adversaries
Relation between the adversaries
Load balancing - identical machines
6.
Load
balancing - related machines
Load balancing - restricted assignment - deterministic and randomized lower
bound
7.
Load
balancing - restricted assignment - upper bound
Load balancing - unrelated machines
Virtual circuit routing
8.
Benefit
problems - financial problems - upper/lower bounds
Admission control and routing - general graphs
9.
Admission
control and routing - general graphs
Admission control on the line - lower bounds
Admission control on the line - classify & randomly select
10. Admission
control on the line - preemptive algorithms
eight variants of admission control on the line:
Deterministic vs. randomized
Non-preemptive vs. preemptive
11. 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
12. 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
13. Picking the
winner
Exercises
Exercises