Algorithmic Methods - 0368.4139

Yossi Azar ( )
1st Semester, 2016/7 - Time: Tues 4-7pm
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 2014 see course2014


New (Previous Exams)

Exam 2014/5

Exam 2012/3

Exam 2010/1


Ex1: ex1

Ex2: ex2

Ex3: ex3



30% exercises
70% exam (on February 7th, 2017 at 9:00am)

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.
Approximation algorithms,

Randomized algorithms, De-randomization,

Distributed and Parallel algorithms,
On-line algorithms.

Course outline (will be updated during the course)

  1. Nov 1:
    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. Nov 8:
    The simplex method
    Initialization of the simplex method
    The dual
  3. Nov 15 :
    The dual
    Complementary slackness
    Economic interpretation
    Feasible vs. Optimal solutions
    Farkas Lemma
    The minimax theorem
  4. Nov 22:
    The Ellipsoid algorithm (Yamanitsky-Levin 1982 variant)
  5. Nov 29:
    The Ellipsoid algorithm with oracle
    Theorem D
    Bi-stochastic matrices
    2-approximation for weighted vertex cover
  6. Dec  6:
    Approximations for MAX-SAT (randomized and deterministic algorithms)
    Approximations for Routing
  7. Dec 13:
    Approximations for Routing
    Approximations for Machine Scheduling (identical+related machines)
    Online Algorithms
  8. Dec 20:
    Reduction from optimality to feasibility (non-polynomial number of constraints)
    Approximations for Machine Scheduling (restricted+unrelated machines)
  9. Dec 27:
    Distributed coloring of a circle (upper bound)
    Distributed coloring of a circle (lower bound)
  10. Jan 3:
    Local ratio - vertex cover
    Local ratio - Interval scheduling
  11. Jan 10:
    Interval scheduling
    Steiner tree
    Generalized Steiner forest
  12. Jan 17:
    Generalized Steiner forest
    PTAS for scheduling
  13. Jan 24:
    PTAS for scheduling

Lecture notes template


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

Last updated January 24, 2017