Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
teaching:proseminar-ads-ws2019 [2019-09-09 15:55]
Nils Kriege [Algorithmic Data Science (WS 2019/2020)]
teaching:proseminar-ads-ws2019 [2019-10-14 10:30] (current)
Nils Kriege [Themen]
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
  
  
 
Last modified: 2019-09-09 15:55 by Nils Kriege
DokuWikiRSS-Feed