2nd Semester, 2022/23 - Time: Mon 4-7pm

School of Computer Science,

For the outline of the course given in 2021 see course2021

Previous Exams

**Exercises**

Ex1**: **ex1

Ex2**: **ex2

Ex3**: **ex3

30%
exercises

70% exam (on July 24, 2023 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

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

Approximation algorithms,

Randomized
algorithms, De-randomization,

Distributed
and Parallel algorithms,

On-line algorithms.

1. **Mar
13:**

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. **Mar 20:**

The simplex method

Initialization of the simplex method

The dual

3. **Mar 27:**

The dual

Complementary slackness

Economic interpretation

Feasible vs. Optimal solutions

Farkas Lemma

The minimax theorem

4. **Apr
17:**

The Ellipsoid algorithm (Yamanitsky-Levin 1982
variant)

5. **Apr
24:**

The Ellipsoid algorithm with oracle

Theorem D

Bi-stochastic matrices

2-approximation for weighted vertex cover

6. **May
1:**

Approximations for MAX-SAT (randomized and deterministic algorithms)

De-randomization

Approximations for Routing

7. **May
8:**

Approximations for Routing

Approximations for Machine Scheduling (identical + related machines)

Online Algorithms

8. **May
15:**

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

Approximations for Machine Scheduling (restricted + unrelated machines)

9. **May
22:**

Distributed coloring of a circle (upper bound)

Distributed coloring of a circle (lower bound)

10. **May
29:**

Local ratio - vertex cover

Local ratio - Interval scheduling

11. **Jun
5: **

Interval scheduling

Steiner tree

Generalized Steiner forest

12. **Jun
12: **

Generalized Steiner forest

PTAS for scheduling

13. **Jun
19: **

PTAS for scheduling

Exercises

14. **Jun
26: extra**

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