Which is the best classified script online

Approximation and online algorithms

Dr. H.-J. Böckenhauer, Dr. D. Komm - Department of Computer Science - FS 2020

Content of the lecture

This learning unit deals with approximate methods for difficult optimization problems and algorithmic approaches for solving online problems as well as the limits of these approaches.

Events

The lecture and the exercises are now taking place as a video conference with the zoom system. The students enrolled for the lecture will each receive an invitation with the meeting number by email.

lectureWednesday13–15CAB G 59Start: February 19, 2020
ExercisesWednesday15–16CAB G 59Start: February 26, 2020

Lecture content

The references in the lecture part about approximation algorithms refer to the book given below Algorithmics for Hard Problems by J. Hromkovi & ccaron ;.

The references in the lecture part about online algorithms refer to the book given below An Introduction to Online Computation by D. Komm as well as the script given below by D. Komm.

  • 19.02.2020 Informal introduction (Definition 4.2.1.1), Approximation algorithms for the metric TSP: spanning tree algorithm, Christofides algorithm (Section 4.3.5 up to before exercise 4.3.5.6)
  • 26.02.2020 Approximation algorithms for vertex covers (Section 4.3.2 up to and including Lemma 4.3.2.5), Set cover (see script below) and weighted vertex cover (Section 4.3.2 from the text after Exercise 4.3.2.18)
  • 04.03.2020 Polynomial approximation schemes (PTAS and FPTAS) (Definition 4.2.1.6), PTAS for the simple backpack problem (SKP) (Section 4.3.4 up to and including Theorem 4.3.4.3), Definition of general backpack problem (KP) and exact algorithm for KP (Section 3.2.2)
  • 11.03.2020 FPTAS for the general backpack problem (KP) (Section 4.3.4 from the text according to Theorem 4.3.4.10), Classification of optimization problems according to their approximability (see script below), pseudopolynomial algorithms and strong NP severity (Sections 3.2.1 and 3.2.4)
  • 18.03.2020 Introduction of non-approximability (Sections 4.4.1 and 4.4.2), AP reductions (Section 4.4.3 up to and including Lemma 4.4.3.5)
  • 25.03.2020 GP reductions (Remainder of Section 4.4.3 from the text after Exercise 4.4.3.9 without Lemma 4.4.3.14)
  • 01.04.2020 Probabilistic verifiers, the PCP theorem and its application to the proof of inapproximability (Section 4.4.4)
  • 08.04.2020 Unique-Games-Conjecture and connection with non-approximability (see script below); Introduction to online algorithms (Preface and section 1.1 to before definition 1.4 in the script; corresponds roughly to section 1.2 to and with Theorem 1.3 in the book)
  • 23.04.2020 Definitions Online Minimization Problems, Online Algorithms, and Competitive Factor; the paging problem; FIFO is (strictly) k-competitive (Script 1.1); no online algorithm is better than k-competitive (Script 1.2)
  • 29.04.2020 Randomized online algorithms and expected competitive factor (Script 1.3); the randomized marking algorithm is (strictly) Hk-competitive(Script 1.4)
  • 06.05.2020 Introduction of lower bounds for randomized online algorithms; Yao's principle (Lemma 1.13 and Theorem 1.15, Script 1.5); lower bound of Hk for the expected costs of randomized online algorithms in paging (Script 1.7)
  • 13.05.2020 The k-Server problem (Script 3.0), the k-Server guess that is randomized k-Server, the greedy algorithm on the line (Script 3.1), Potential functions (Script 3.2), the double coverage algorithm (Script 3.3)
  • 20.05.2020 Introduction to advice complexity (Script 4.0), the advice complexity of paging (Script 4.1, except Proposition 4.7 all propositions without evidence), the advice complexity of k-Server (Script 4.2, all sentences without evidence)
  • 27.05.2020 Advice and randomization (Script 6.0), the online backpack problem (Script 5.0) and deterministic (Script 5.1), Advice- (Script 5.2 without the proof of Theorem 5.8) and randomized (Script 5.4, without the proof of Theorems 5.10, 5.11) Algorithms

Examination material

The examination material includes everything that was dealt with in the lecture, as well as the material of the exercise sheets and solutions.

Scripts

Here there are links to scripts for topics of the lecture that are not included in this form in the specified literature.

Exercises

literature

  • J. Hromkovič: Algorithmics for Hard Problems, 2004, Springer-Verlag, ISBN: 3-540-44134-4.
  • D. Come: An Introduction to Online Computation: Determinism, Randomization, Advice, 2016, Springer-Verlag, ISBN: 3-319-42747-4;
    a script containing parts of the book is available online.

Contact: Dr. Dennis Come on, Disclaimer of liability, last change: 28.05.2020 13:50.