## Algorithmic Methods
- 0368.4139

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

### Grade:

30%
exercises

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

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

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

##### Last
updated Jan 26, 2021