## On-line and
Approximation Algorithms - 0368.4041

### EXAM is on July 1,
2024

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

### Grade:

30% exercises

70% exam

### Exercises:

Exercise1 (Due on Jun xx, 2024)

Exercise2 (Due on Jul xx, 2024)

Exercise3 (Due on Aug xx, 2024)

### Lecture notes

### 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

##### Last updated Apr 2,
2024