direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Seminar on Graphs and Algorithms

In this seminar we cover various aspects of algorithmic problems on graphs and related combinatorial structures. The goal is make students familiar with recent developments in this area, and to teach them the necessary tools to explore scientific papers and literature on their own. Moreover, students will aquire important skills for presenting these technical results to a wider audience.

Prerequisites

The purpose of this seminar is to read and understand recent results from the literature on graphs and algorithms. Participants are expected to have some experience with the analysis of advanced algorithms (e.g. from an ADM III course).

Important dates

The first meeting will take place on April 21, 2016, 14:15, in room MA 544.

The second meeting where papers are assigned to students and general guidelines are discussed will take place on April 28, 2016, 14:15, in room MA 544. Please have a look at the list of papers below to see which topic might be of interest to you, and pick your 3 favourite papers. The number of participants of the seminar is limited to 16. If more people show up, then we will make a random selection during the second meeting. The assignment of students to papers will be done based on the preferences of the students. The guidelines presented in the second meeting can be found here.

On May 12, 2016, 14:15, in room MA 544, Max and Torsten will give a presentation of 30 minutes each, to give a live demonstration of superb presentation skills. Max' slides (with some of the figures removed) can be found here.

Each participant will give a 5-minute introductory presentation on May 19, 2016, 14:15, in room MA 544.

The presentation slides have to be handed in before June 16, 2016 for a final check.

The seminar will be held as a block seminar on June 30 & July 01, 2016, 10:00-19:00 in MA 212.

List of papers

  1. T. Chan, Improved Deterministic Algorithms for Linear Programming in Low Dimensions, SODA 2016
  2. (Axel-Bernhard W.) S. Arya and D. Mount, A Fast and Simple Algorithm for Computing Approximate Euclidean Minimum Spanning Trees, SODA 2016
  3. (Felix S.) C. Annamalai, Finding Perfect Matchings in Bipartite Hypergraphs, SODA 2016
  4. G. Braun, J. Brown-Cohen, A. Huq, S. Pokutta, P. Raghavendra, A. Roy, B. Weitz, D. Zink, The matching problem has no small symmetric SDP, SODA 2016
  5. (Aron H.) D. Straszak and N. Vishnoi, Natural Algorithms for Flow Problems, SODA 2016
  6. (Julian R.) M. Chudnovsky, J. Goedgebeur, O. Schaudt and M. Zhong, Obstructions for three-coloring graphs with one forbidden induced subgraph, SODA 2016
  7. (Jonas N.) G. Joret, P. Micek and V. Wiechert, Sparsity and dimension, SODA 2016
  8. (Andre G.) F. Ruskey and A. Williams, The coolest way to generate combinations, Discrete Mathematics, Volume 309, Issue 17(6), 2009, 5305–5320 (link)
  9. (Christopher D.) F. Ruskey, Adjancent interchange generation of combinations, Journal of Algorithms, Volume 9, Issue 2, 1988, 162-180 (link)
  10. (Jakob B.) A. Proskurowski and F. Ruskey, Generating binary trees by transpositions, Journal of Algorithms, Volume 11, Issue 1, 1990, 68-84 (link)
  11. (Sebastian S.) T. Roughgarden, Barriers to Near-Optimal Equilibria, FOCS 2014 (link)
  12. (Jan-Philipp E.) M. Feldman, N. Immorlica, B. Lucier, T. Roughgarden, V. Syrgkanis, The Price of Anarchy in Large Games, STOC 2016 (link)
  13. V. Bilo, M. Flammini, L. Moscardelli, The price of stability for undirected broadcast network design with fair cost allocation is constant, Games and Economic Behavior, available online (link)
  14. G. Christodoulou, A. Sgouritsa, Designing Networks with Good Equilibria under Uncertainty, SODA 2016 (link)
  15. (Alexander W.) S. Alaei, J. Hartline, R. Niazadeh, E. Pountourakis, Y. Yuan, Optimal Auctions vs. Anonymous Pricing, FOCS 2015 (link)
  16. (Stefanie W.) R. Gopalakrishnan, J. Marden, A. Wierman, Potential Games are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games, Mathematics of Operations Research, 2014 (link)
  17. (Julian S.) H. Chen, T. Roughgarden, G. Valiant, Designing Network Protocols for Good Equilibria, SIAM Journal on Computing, 2010 (link)
  18. (Jakob F.) I. Caragiannis, A. Fanelli, N. Gravin, A. Skopalik, Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games, FOCS 2011, (link)
  19. (Paul N.) I. Ashlagi, F. Fischer, I. Kash, A. Procaccia, Mix and match: A strategyproof mechanism for multi-hospital kidney exchange, Games and Economic Behavior, 2015 (link)
  20. (Judith K.) O. Göbel, M. Hoefer, T. Kesselheim, T. Schleiden, B. Vöcking, Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods, ICALP 2014, (link)

Schedule of Talks

Schedule
Thursday, June 30, MA 212
Student
Paper
10:00-10:45
Andre G.
F. Ruskey and A. Williams, The coolest way to generate combinations, Discrete Mathematics, Volume 309, Issue 17(6), 2009, 5305–5320
10:50-11:35
Christopher D.
F. Ruskey, Adjacent interchange generation of combinations, Journal of Algorithms, Volume 9, Issue 2, 1988, 162-180
11:40-12:25
Jakob B.
A. Proskurowski and F. Ruskey, Generating binary trees by transpositions, Journal of Algorithms, Volume 11, Issue 1, 1990, 68-84
14:00-14:45
Axel-Bernhard W.
S. Arya and D. Mount, A Fast and Simple Algorithm for Computing Approximate Euclidean Minimum Spanning Trees, SODA 2016
14:50-15:35
Felix S.
C. Annamalai, Finding Perfect Matchings in Bipartite Hypergraphs, SODA 2016
15:40-16:25
Julian R.
M. Chudnovsky, J. Goedgebeur, O. Schaudt and M. Zhong, Obstructions for three-coloring graphs with one forbidden induced subgraph, SODA 2016
16:30-17:15
Julian S.
H. Chen, T. Roughgarden, G. Valiant, Designing Network Protocols for Good Equilibria, SIAM Journal on Computing, 2010
17:20-18:05
Jonas N.
G. Joret, P. Micek and V. Wiechert, Sparsity and dimension, SODA 2016
18:10-18:55
Aron H.
D. Straszak and N. Vishnoi, Natural Algorithms for Flow Problems, SODA 2016
Friday, July 01, MA 212
10:00-10:45
Judith K.
O. Göbel, M. Hoefer, T. Kesselheim, T. Schleiden, B. Vöcking, Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods, ICALP 2014
10:50-11:35
Sebastian S.
T. Roughgarden, Barriers to Near-Optimal Equilibria, FOCS 2014
11:40-12:25
Jan-Philipp E.
M. Feldman, N. Immorlica, B. Lucier, T. Roughgarden, V. Syrgkanis, The Price of Anarchy in Large Games, STOC 2016
14:00-14:45
Alexander W.
S. Alaei, J. Hartline, R. Niazadeh, E. Pountourakis, Y. Yuan, Optimal Auctions vs. Anonymous Pricing, FOCS 2015
14:50-15:35
Stefanie W.
R. Gopalakrishnan, J. Marden, A. Wierman, Potential Games are Necessary to Ensure Pure Nash Equilibria in Cost Sharing Games, Mathematics of Operations Research, 2014
15:40-16:25
Jakob F.
I. Caragiannis, A. Fanelli, N. Gravin, A. Skopalik, Efficient Computation of Approximate Pure Nash Equilibria in Congestion Games, FOCS 2011
16:30-17:15
Paul N.
I. Ashlagi, F. Fischer, I. Kash, A. Procaccia, Mix and match: A strategyproof mechanism for multi-hospital kidney exchange, Games and Economic Behavior, 2015

 

 

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe