Algorithmic Methods - 0368.4139

Yossi Azar ( )
2nd Semester, 2022/23 - Time: Mon 4-7pm
School of Computer Science,
Tel-Aviv University


For the outline of the course given in 2021 see course2021

Previous Exams

Exam 2020/1

Exam 2018/9

Exam 2016/7

Exam 2014/5

Exam 2012/3

Exam 2010/1


Ex1: ex1

Ex2: ex2

Ex3: ex3


30% exercises
70% exam (on July 24, 2023 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

1.      Mar 13:
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.      Mar  20:
The simplex method
Initialization of the simplex method
The dual

3.      Mar  27:
The dual
Complementary slackness
Economic interpretation
Feasible vs. Optimal solutions
Farkas Lemma
The minimax theorem

4.      Apr 17:
The Ellipsoid algorithm (Yamanitsky-Levin 1982 variant)

5.      Apr 24:
The Ellipsoid algorithm with oracle
Theorem D
Bi-stochastic matrices
2-approximation for weighted vertex cover

6.      May 1:
Approximations for MAX-SAT (randomized and deterministic algorithms)
Approximations for Routing

7.      May 8:
Approximations for Routing
Approximations for Machine Scheduling (identical + related machines)
Online Algorithms

8.      May 15:
Reduction from optimality to feasibility (non-polynomial number of constraints)
Approximations for Machine Scheduling (restricted + unrelated machines)

9.      May 22:
Distributed coloring of a circle (upper bound)
Distributed coloring of a circle (lower bound)

10.  May 29:
Local ratio - vertex cover
Local ratio - Interval scheduling

11.  Jun 5:
Interval scheduling
Steiner tree
Generalized Steiner forest

12.  Jun 12:
Generalized Steiner forest
PTAS for scheduling

13.  Jun 19:
PTAS for scheduling

14.  Jun 26: extra


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 Jun 28, 2023