direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments


Due to the current COVID-19 pandemic, some students may have to give their final presentation online. Otherwise, the seminar takes place on July 2nd from 9:00-15:00 in room MA313. Here is the zoom-link for those students who cannot attend in person, and for visitors:

Zoom-Link for the final presentations:

Time: July 2, 2020, 09:30-15:00

Join Zoom Meeting
Meeting ID: 931 0792 9051
Password: 123363



Seminar on Graphs, Algorithms and Optimization

In this seminar we cover various aspects of algorithmic problems on graphs and combinatorial optimization problems. The goal is to 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 acquire important skills for presenting these technical results to a wider audience.


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

Talk schedule

Duration of each talk is 40 minutes, plus 5 minutes for questions/setup for the next speaker.

Preliminary schedule
Thursday, July 2
Paper 6 (Alfons R.)
Paper 8 (Xueyi G.)
Paper 9 (Lara G.)
Paper 13 (Sandro R.)
Lunch break
Paper 1 (Liliana G.)
Paper 12 (Berit O.)

Important dates

The first meeting will take place on April 23, 2020, 10:15. During this meeting, we will present the papers available for this seminar. Please have a look at the list of papers below to see which topic might be of interest to you, and pick your 5 favourite papers.

The second meeting where papers are assigned to students and general guidelines are discussed will take place on April 30, 2020, 10:15.The slides used to present those guidelines are here. The number of participants of the seminar is strictly limited to 16. If more people show up, then we will make a random selection before the second meeting. The assignment of students to papers will be done based on the preferences of the students.

Each participant will give a 5-minute introductory presentation on May 28, 2020, 10:15. Please send us the slides for the 5-minute presentation in PDF format beforehand by email.

The seminar will be held as a block seminar on July 2, 2020, 09:00-16:00 in MA 313. A PDF version of the slides for the final presentation has to be handed in before June 24, 2020 for a final check. All participants must be present during all the talks.

List of papers

  1. () Englert, M., Mezlaf, D., & Westermann, M. (2018). Online makespan scheduling with job migration on uniform machines. In 26th Annual European Symposium on Algorithms (ESA 2018) (link)
  2. () Lattanzi, S., Lavastida, T., Moseley, B., & Vassilvitskii, S. (2020). Online Scheduling via Learned Weights. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1859-1877) (link)
  3. () Garg, N., Gupta, A., Kumar, A., Singla, S. (2019). Non-clairvoyant Precedence Constrained Scheduling. In 46th International Colloquium on Automata, Languages, and Programming (63) (link)
  4. () Bougeret, M., Pessoa, A. A., & Poss, M. (2019). Robust scheduling with budgeted uncertainty. Discrete Applied Mathematics, 261, 93-107 (link)
  5. () Roy, A., & Pokutta, S. (2017). Hierarchical clustering via spreading metrics. The Journal of Machine Learning Research, 18(1), 3077-3111 (link)
  6. () Cohen-Addad, V., Kanade, V., Mallmann-Trenn, F., & Mathieu, C. (2019). Hierarchical clustering: Objective functions and algorithms. Journal of the ACM (JACM), 66(4), 1-42. (link)
  7. () Charikar, M., Chatziafratis, V., & Niazadeh, R. (2019). Hierarchical clustering better than average-linkage. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 2291-2304). (link)
  8. () Iwata, S., Tetali, P., & Tripathi, P. (2012). Approximating minimum linear ordering problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (pp. 206-217). (link)
  9. () Angel, E., Bampis, E., & Gourvès, L. (2006). Approximation algorithms for the bi-criteria weighted MAX-CUT problem. Discrete Applied Mathematics, 154, 1685–1692. (link)
  10. () Torrico, A., Singh, M., & Pokutta, S. (2019). On the Unreasonable Effectiveness of the Greedy Algorithm: Greedy Adapts to Sharpness. In Proceedings of the OPTML19 Workshop, paper 16. (link)
  11. () Andoni, A., Gupta, A., & Krauthgamer, R. (2014, January). Towards (1+∊)-Approximate Flow Sparsifiers. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms (pp. 279-293). (link)
  12. () Frascaria, D. & Olver, N. (2020). Algorithms for flows over time with scheduling costs. IPCO 2020 (link)
  13. () Gallo, G., Grigoriadis, M. D., & Tarjan, R. E. (1989). A fast parametric maximum flow algorithm and applications. SIAM Journal on Computing, 18(1), 30-55. (link)
  14. () Su, W., Boyd, S., & Candes, E. (2014). A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights. In Advances in Neural Information Processing Systems (pp. 2510-2518). (link)
  15. () Fercoq, O., Gramfort, A., & Salmon, J. (2015, June). Mind the duality gap: safer rules for the Lasso. In International Conference on Machine Learning (pp. 333-342). (link)
  16. () Mairal, J., & Yu, B. (2012, June). Complexity analysis of the lasso regularization path. In Proceedings of the 29th International Conference on Machine Learning (pp. 1835-1842). (link)



Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe

Diese Seite verwendet Matomo für anonymisierte Webanalysen. Mehr Informationen und Opt-Out-Möglichkeiten unter Datenschutz.