On-line and Approximation Algorithms - 0368.4041

-----

Yossi Azar ( azar@tau.ac.il )
2nd Semester, 2013/14 - Wed 16-19, Orenstein 111
School of Computer Science,
Tel-Aviv University

-----

EXAM is on June 24, 2014

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

Grade:

30% exercises
70% exam

Exercises:

Exercise3 (Due on May 28)
Exercise2 (Due on Apr 23)
Exercise1 (Due on Mar 26)

Lecture notes template

noteTemplate.tex
noteTemplate.pdf

Lecture notes

Class-1 on 2014
Class-2 on 2014
Class-3 on 2014
Class-4 on 2014
Class-5 on 2014
Class-6 on 2014
Class-7 on 2014
Class-8 on 2014
Class-9 on 2014
Class-10 on 2014
Class-11 on 2014
Class-12 on 2014
Class-13 on 2014

For the outline of the course given in 2011/12 see course2011/12

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. Feb 19, 2014 :
    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. Feb 26, 2014 :
    List update - definitions
    List update - various algorithms
    List update -2 competitive MF algorithm
    List update - 2 lower bound
  3. Mar 5, 2014 :
    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. Mar 12, 2014 :
    Randomized algorithms
    Quick sort, primality test, max cut
    Ski rental - randomized upper/lower bounds
    Survival game
    Paging - 2H(k) competitive randomized marking algorithm
  5. Mar 19, 2014 :
    Paging - H(k) randomized lower bound
    Oblivious, adaptive on-line and off-line adversaries
    Relation between the adversaries
    Load balancing - identical machines
  6. Mar 26, 2014 :
    Load balancing - related machines
    Load balancing - restricted assignment - deterministic and randomized lower bound
  7. Apr 2, 2014 :
    Load balancing - restricted assignment - upper bound
    Load balancing - unrelated machines
    Virtual circuit routing
  8. Apr 23, 2014 :
    Benefit problems - financial problems - upper/lower bounds
    Admission control and routing - general graphs
  9. Apr 30, 2014 :
    Admission control and routing - general graphs
    Admission control on the line - lower bounds
    Admission control on the line - classify & randomly select
  10. May 7, 2014 :
    Admission control on the line - preemptive algorithms
    eight variants of admission control on the line:
    Deterministic vs. randomized
    Non-preemptive vs. preemptive
  11. May 14, 2014 :
    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. May 21, 2014:
    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. May 28, 2014:
    Picking the winner
    Exercises
  14. Jun 11, 2014:
    Choice of two
    Exercises

Last updated Feb 12, 2014