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