## Algorithmic Methods - 0368.4139

#### Yossi Azar ( azar@tau.ac.il ) 1st Semester, 2018/9 - 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 2016 see course2016

New (Previous Exams)

Exercises

Ex1: ex1

Ex2:

Ex3: ex3

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