Hier finden Sie eine Übersicht über die angebotenen Themen des Proseminars. Weitere Themen sind auf Absprache möglich.

Die Seitenzahlen beziehen sich auf die folgenden Quellen:

[1] Giorgio Ausiello, M. Protasi, A. Marchetti-Spaccamela, G. Gambosi, P. Crescenzi, and V. Kann. 1999. Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties (1st ed.). Springer-Verlag New York, Inc., Secaucus, NJ, USA.

[2] Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press, New York, NY, USA.

A. Approximation: Grundlagen und Techniken

1. Wiederholung GTI, formale Grundlagen ([1], S. 17-33)

2. Greedy-Algorithmen ([1], S. 40-47, optional S. 47-50)

3. Sequentielle Algorithmen ([1], S. 50-60)

4. Lokale Suche und dynamische Programmierung ([1], S. 61-65, 69-74)

5*. Lineare Programmierung ([1], S. 65-69, 361-365)

B. Approximation und Komplexität

6. Approximation mit konstanter Güte ([1], S. 90-99, optional S. 100-102)

7. Approximationsschemas 1: PTAS ([1], S. 102-105, 110-111, dazu wahlweise S. 105-107
oder S. 107-110)

8. Approximationsschemas 2: FPTAS; starke NP-Vollständigkeit ([1], S. 111-116)

9*. Randomisierte Approximation ([1], S. 74-76,153-162)

C. Online-Algorithmen

10. List Accessing 1: Obere Schranken ([2], S. 1-10)

11. List Accessing 2: Untere Schranken und Listenfaktorisierung ([2], S. 10-19)

12*. Randomisiertes List Accessing ([2] S. 23-29)

13. Paging ([2] S. 33-40 ohne 3.5.2 und 3.7)

14*. Randomisiertes Paging ([2] S. 44-52, optional 4.4)

15. Paging mit Zugriffsgraphen ([2] S. 54-62 ohne Sätze 5.1, 5.9, 5.10; optional S. 62-64)

16. Load Balancing 1: Permanente Jobs ([2] S. 201-210)

17. Load Balancing 2: Virtual Circuit Routing; Temporäre Jobs ([2] S. 210-218)