Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Seminar Randomisierte Algorithmen

im Sommersemester 2016

Veranstalter:Prof. Dr. Christian Sohler
Termine: Montag16-18 Uhr OH14, R104
Beginn: Mo, 11.04.2016


[Inhalt] [Themen und Literatur] [LSF]


Inhalt

Im Seminar werden wir uns mit dem Thema randomisierte Algorithmen beschäftigen. Der erste Besprechungstermin findet in der ersten Vorlesungswoche zum Seminartermin statt. Dort werden auch die Themen vergeben.


Themen und Literatur

Eine unvollständige Auswahl von Themen finden Sie unten stehend:

Randomisierte Datenstrukturen:
  • Raimund Seidel, Cecilia Aragon. Randomized Search Trees. Algorithmica 16, pp. 464-497, 1996.
  • Mikkel Thorup, Uri Zwick. Approximate Distance Oracles. JACM, 2005.
Randomisierte Exakte Algorithmen:
  • Jiri Matousek, Micha Sharir, Emo Welzl. A Subexponential Bound for Linear Programming. Algorithmica 16(4/5): 498-516, 1996.
  • D. Karger, P. Klein, R. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. JACM, 1995.
Randomisierte Approximationsalgorithmen:
  • Anupam Gupta, Amit Kumar and Tim Roughgarden. Simpler and better approximation algorithm for network design. 35th STOC, 2003.
Analyse probabilistischer Prozesse:
  • Berthold Vöcking. How asymmetry helps load balancing. JACM, 50(4):568-589, 2003.
Property Testing/Sublinearzeitalgorithmen:
  • Tugkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren Smith, Patrick White. Testing Closeness of Discrete Distributions. JACM 60(1):4, 2013.
  • Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan. Approximating the Minimum Spanning Tree Weight in Sublinear Time. SICOMP 34(6):1370-1379, 2005.
  • Mihai Badoiu, Artur Czumaj, Piotr Indyk, Christian Sohler. Facility Location in Sublinear Time. ICALP 2005: 866-877.
Datenstromalgorithmen:
  • Noga Alon, Yossi Matias, Mario Szegedy. The space complexity of approximating the frequency moments. JCSS 58, 137-147, 1999.
  • Ke Chen. On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications. SICOMP 39(3):923-947, 2009.



Das Seminar Randomisierte Algorithmen im Vorlesungsverzeich LSF.



Letzte Änderung am 29.03.2016 von A. Munteanu