Differences
This shows you the differences between two versions of the page.
|
teaching:proseminar-ads-ws2019 [2019-09-09 15:55] |
teaching:proseminar-ads-ws2019 [2019-10-14 10:30] |
||
|---|---|---|---|
| Line 29: | Line 29: | ||
| ===== Themen ===== | ===== Themen ===== | ||
| - | <WRAP todo center round big 60% bigger> | + | ^ Nr. ^ Thema ^ Teilnehmer ^ Quellen ^ |
| - | Eine Liste möglicher Themen und geeignete Literatur werden rechtzeitig vor der Themenvergabe im Rahmen der Vorbesprechung bekanntgegeben. | + | |**Zuordnungsprobleme** |||| |
| - | </WRAP> | + | | 1| Theoretische Grundlagen: Heiratssatz, perfekte Matchings | Jan Schülling | 1, Abschnitt 2.1 | |
| + | | 2| Theoretische Grundlagen: Das Assignment Polytop | | 1, Abschnitt 2.2 | | ||
| + | | 3| Matchings in bipartitten Graphen: Grundlagen | Jin Ke | 1, Abschnitt 3.1 und 3.2 | | ||
| + | | 4| Algorithmus von Hopcroft und Karp | Rand Serjawi | 1, Abschnitt 3.3 | | ||
| + | | 5| Matchings in konvexen bipartiten Graphen | Andreas Rüb | 1, Abschnitt 3.5 | | ||
| + | | 6| Das lineare Assignment Problem: Die ungarische Methode | Hendrik Zemke | 1, Abschnitt 4.1 und 4.2 (ohne 4.2.3) | | ||
| + | | 7| Die ungarische Methode mittels kürzester Wege | Burak Özkan | 1, Abschnitt 4.4 | | ||
| + | | 8| Das quadratische Assignment Problem | Daniel Lensker | 1, Abschnitt 7.1 | | ||
| + | |**Transportprobleme** |||| | ||
| + | | 9| Die Probleme von Monge und Kantorovich | Fatima Taleb | 2, Abschnitt 2 | | ||
| + | | 10| Algorithmen: LP und Flußformulierungen | Peter Tisoczki | 2, Abschnitt 3 | | ||
| + | |**Optimale Spannbäume** |||| | ||
| + | | 11| Single-linkage Clustering | George Mamar | 9 | | ||
| + | | 12| Algorithmen von Borůvka und Jarnik | Carsten Kellner | 10 | | ||
| + | |**Spektren von Graphen** |||| | ||
| + | | 13| Graph-Spektrum | Josef Schneider | 11, Abschnitt 1.1-1.7 | | ||
| + | | 14| Eigenwerte und Eigenvektoren | Jonathan Liening | 11, Abschnitt 3.1-3.6 | | ||
| + | | 15| Anwendungen von Eigenvektoren | | 11, Abschnitt 3.13 | | ||
| + | |**Ausgewählte Themen** |||| | ||
| + | | 16| PageRank | Mohamad Nassar | 3 | | ||
| + | | 17| Network Alignment: IsoRank and NSD | Benjamin Biehler | 4 | | ||
| + | | 18| Kendal's Tau und seine Berechnung | Roman Leis | 5, 6 | | ||
| + | | 19| Die Softassign und Softmax Methode | Jonas Grobe | 7 | | ||
| + | | 20| Optimale Schnitte für Baummetriken | | 8 | | ||
| + | | 21| Locality-Sensitive Hashing | Sergius Becker | 3 | | ||
| + | |||
| + | * [1] R.E. Burkard, M. Dell'Amico, and S. Martello. Assignment Problems. SIAM, 2012. | ||
| + | * [2] G. Peyré, M. Cuturi. [[http://dx.doi.org/10.1561/2200000073|Computational Optimal Transport]]. Foundations and Trends in Machine Learning 11(5-6): 355-607, 2019. | ||
| + | * [3] J. Leskovec, A. Rajaraman, J.D. Ullman. [[http://infolab.stanford.edu/~ullman/mmds/book.pdf|Mining of Massive Datasets]], 2014. | ||
| + | * [4] G. Kollias, S. Mohammadi, and A. Grama. Network similarity decomposition (NSD): A fast and scalable approach to network alignment. IEEE Tranactions on Knowledge and Data Engineering, 24(12), 2012. | ||
| + | * [5] H. Abdi. Kendall rank correlation. Encyclopedia of Measurement and Statistics. Thousand Oaks (CA): Sage, 2007. | ||
| + | * [6] W. Knight. A Computer Method for Calculating Kendall's Tau with Ungrouped Data. Journal of the American Statistical Association. 61 (314): 436–439, 1966. | ||
| + | * [7] S. Gold, A. Rangarajan. Softassign versus Softmax: Benchmarks in Combinatorial Optimization. NIPS: 626-632, 1995. | ||
| + | * [8] M. Karpinski, A. Lingas, D. Sledneu. Optimal cuts and partitions in tree metrics in polynomial time. Inf. Process. Lett. 113(12): 447-451, 2013. | ||
| + | * [9] J.C. Gower, G.J. Ross. Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society, Series C. 18 (1): 54–64, 1969. | ||
| + | * [10] J. Nešetřil, H. Nešetřilová. [[https://www.math.uni-bielefeld.de/documenta/vol-ismp/30_nesetril-nesetrilova.pdf|The Origins of Minimal Spanning Tree Algorithms - Borůvka und Jarnik]], Documenta Mathematica, 2012 | ||
| + | * [11] A.E. Brouwer, W.H. Haemers: [[https://www.win.tue.nl/~aeb/2WF02/spectra.pdf|Spectra of Graphs - Monograph]], Springer, 2011 | ||