1st Semester, 2016/7 - Time: Tues 4-7pm

School of Computer Science,

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

30%
exercises

70% exam (on February 7^{th}, 2017 at 9:00am)

(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

Linear
Programming - simplex, duality, the ellipsoid algorithm, applications.

Approximation algorithms,

Randomized
algorithms, De-randomization,

Distributed
and Parallel algorithms,

On-line algorithms.

**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

noteTemplate.tex

noteTemplate.pdf

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