1st Semester, 2018/9 - Time: Mon 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 2016 see course2016

New (Previous Exams)

**Exercises**

Ex1**: **ex1

Ex2**: **ex2

Ex3**:** ex3

30%
exercises

70% exam (on January 21^{st}, 2019 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.

**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**Oct 22:**

The simplex method

Initialization of the simplex method

The dual**Oct 29:**

The dual

Complementary slackness

Economic interpretation

Feasible vs. Optimal solutions

Farkas Lemma

The minimax theorem**Nov 5:**

The Ellipsoid algorithm (Yamanitsky-Levin 1982 variant)**Nov 12:**

The Ellipsoid algorithm with oracle

Theorem D

Bi-stochastic matrices

2-approximation for weighted vertex cover**Nov 19:**

Approximations for MAX-SAT (randomized and deterministic algorithms)

De-randomization

Approximations for Routing**Nov 26:**

Approximations for Routing

Approximations for Machine Scheduling (identical+related machines)

Online Algorithms**Dec 3:**

Reduction from optimality to feasibility (non-polynomial number of constraints)

Approximations for Machine Scheduling (restricted+unrelated machines)**Dec 10:**

Distributed coloring of a circle (upper bound)

Distributed coloring of a circle (lower bound)**Dec 17:**

Local ratio - vertex cover

Local ratio - Interval scheduling**Dec 24:**

Interval scheduling

Steiner tree

Generalized Steiner forest**Dec 31:**

Generalized Steiner forest

PTAS for scheduling**Jan 7:**

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