Algorithmic Methods - 0368.4139

Yossi Azar ( azar@tau.ac.il )
1st Semester, 2010 -Mon 16-19, Schreiber 7
School of Computer Science,
Tel-Aviv University

-----

This page will be modified during the course, and will outline the classes.
For the outline of the course given in 2004 see course2004

Grade:

30% exercises
70% exam

Exercises:

Exercise1 (Due on Nov 22)
Exercise2 (Due on Dec 13)
Exercise3 (Due on Jan 3)
Exam

Lecture notes template

noteTemplate.tex
noteTemplate.pdf

Lecture notes

Class-1 on 18.10.2010
Class-2 on 25.10.2010
Class-3 on 1.11.2010
Class-4 on 8.11.2010
Class-5 on 15.11.2010
Class-6 on 22.11.2010
Class-7 on 29.11.2010
Class-8 on 6.12.2010
Class-9 on 13.12.2010
Class-10 on 20.12.2010
Class-11 on 27.12.2010
Class-12 on 3.1.2011
Class-13 on 10.1.2011

Text books (only couple of chapters from each book)

(1) Linear Programming by H. Karloff, Birkhauser, 1991.
(2) Introduction to Algorithms by T. Cormen, C. Leiserson and R. Rivest, MIT Press, 1990
(3) Approximation Algorithms for NP-hard problems edited by S. Hochbaum, PWS Publishing company, 1997.
(4) Approximation Algorithms by Vijay Vazirani, Springer, 2003.
(5) Survey on Local Ratio Survey

Course syllabus:

Linear Programming - simplex, duality, the ellipsoid algorithm, applications.
Discrete Fourier transform,
Distributed and Parallel algorithms,
Approximation algorithms,
Randomized algorithms, De-randomization,
On-line algorithms.

Course outline (will be updated during the course)

  1. Oct 18 :
    Introduction
    Examples of linear programming problems
    Basic definitions (canonical, standard, general forms, polyhedron, polytope, basic feasible solution)
    Theorems A, B, C on polyhedrons and their vertices
  2. Oct 25 :
    Theorem C
    The simplex method
    Initialization of the simplex method
    The dual
  3. Nov 1 :
    The dual
    Complementary slackness
    Economic interpretation
    Feasible vs. Optimal solutions
    Farkas Lemma
    The minimax theorem
  4. Nov 8 :
    The minimax theorem
    The Ellipsoid algorithm (Yamanitsky-Levin 1982 variant)
  5. Nov 15 :
    The Ellipsoid algorithm with oracle
    Theorem D
    Bi-stochastic matrices
    2-approximation for weighted vertex cover
  6. Nov 22 :
    Approximations for MAX-SAT (randomized and deterministic algorithms)
    De-randomization
    Approximations for Routing
  7. Nov 29 :
    Approximations for Routing
    Approximations for Machine Scheduling (identical+related machines)
    Online Algorithms
  8. Dec 6 :
    Reduction from optimality to feasibility (non-polynomial number of constraints)
    Approximations for Machine Scheduling (restricted+unrelated machines)
  9. Dec 13 :
    Distributed coloring of a circle (upper bound)
    Distributed coloring of a circle (lower bound)
  10. Dec 20 :
    Local ratio - vertex cover
    Local ratio - Interval scheduling
  11. Dec 27:
    Interval scheduling
    Steiner tree
    Generalized Steiner forest
  12. Jan 3:
    Generalized Steiner forest
    PTAS for scheduling
  13. Jan 10:
    PTAS for scheduling
    Exercises
Last updated January 17, 2011