2nd Semester, 2020/21 - 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 2018 see course2018

**Exercises**

Ex1**: **ex1

Ex2**: **ex2

30%
exercises

70% exam (on July 1^{st}, 2021 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.

**Mar 8:**

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**Mar 15:**

The simplex method

Initialization of the simplex method

The dual**Mar 22:**

The dual

Complementary slackness

Economic interpretation

Feasible vs. Optimal solutions

Farkas Lemma

The minimax theorem**Apr 5:**

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

The Ellipsoid algorithm with oracle

Theorem D

Bi-stochastic matrices

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

Approximations for MAX-SAT (randomized and deterministic algorithms)

De-randomization

Approximations for Routing**Apr 26:**

Approximations for Routing

Approximations for Machine Scheduling (identical+related machines)

Online Algorithms**May 3:**

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

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

Distributed coloring of a circle (upper bound)

Distributed coloring of a circle (lower bound)**May 24:**

Local ratio - vertex cover

Local ratio - Interval scheduling**May 31:**

Interval scheduling

Steiner tree

Generalized Steiner forest**Jun 7:**

Generalized Steiner forest

PTAS for scheduling**Jun 14:**

PTAS for scheduling

Exercises

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