Algorithmic Methods - 0368.4139

Yossi Azar ( azar@tau.ac.il )
1st Semester, 2014/5 - Time: Mon 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 2012 see course2012

New (Previous Exams)

Exam 2012/3

Exam 2010/1

Exercises

Ex1: ex14-1

Ex2: ex14-2

Ex3: ex14-3

Grade:

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

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

Last updated October 13, 2014