direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Seminar on Graphs, Algorithms and Optimization

In this seminar we cover various aspects of algorithmic problems on graphs and related combinatorial structures. 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.

We also indicate another related seminar on Algorithmic Mixed-Integer Programming taking place at the FU.


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).

Important dates

The first meeting will take place on April 8, 2019, 10:15, in room MA 376. 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 29, 2019, 10:15, in room MA 376. The number of participants of the seminar is limited to 18. 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. The guidelines presented during this meeting can be downloaded here.

Each participant will give a 5-minute introductory presentation on May 27, 2019, 10:15, in room MA 376. 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 June 13 & 14, 2019, 09:00-16:00 in MA 313. A PDF version of the slides for the final presentation has to be handed in before June 10, 2019 for a final check. All participants must be present during all the talks.

List of papers

  1. (Rolf W.) Azar, Y., & Epstein, A. (2005). Convex programming for scheduling unrelated parallel machines. STOC 2005 (pp. 331-337) (link).
  2. (Yvonne M.) Kalaitzis, C., Svensson, O., & Tarnawski, J. (2017). Unrelated machine scheduling of jobs with uniform smith ratios. SODA 2017 (pp. 2654-2669) (link).
  3. (Lukas S.) Gupta, A., Kumar, A., Nagarajan, V., & Shen, X. (2018). Stochastic load balancing on unrelated machines. SODA 2018 (pp. 1274-1285) (link).
  4. (Rick G.) Gupta, V., Moseley, B., Uetz, M., & Xie, Q. (2017). Greed Works-Online Algorithms For Unrelated Machine Stochastic SchedulingarXiv preprint arXiv:1703.01634 (link).
  5. (Armin F.) Feigenbaum, I., & Johnson, M.P. (2015). Selflish Knapsack. arXiv preprint arXiv:1510.07358 (link).
  6. (Minh P.) Olver, N., & Végh, L. A. (2017). A simpler and faster strongly polynomial algorithm for generalized flow maximization, STOC 2017 (pp. 100-111) (link).
  7. (Tim G.) Arora, S., Rao, S., & Vazirani, U. (2009). Expander flows, geometric embeddings and graph partitioningJournal of the ACM (JACM)56(2):5 (link).
  8. (Elaine Z.) Charikar, M., & Chatziafratis, V. (2017). Approximate hierarchical clustering via sparsest cut and spreading metrics, SODA 2017 (pp. 841-854) (link)
  9. (Hannes R.) Boczkowski, L., Korman, A., & Rodeh, Y. (2018). Searching a Tree with Permanently Noisy Advice, ESA 2018 (link)
  10. (Sebastian O.) Singh, M., & Xie, W. (2018). Approximate positive correlated distributions and approximation algorithms for D-optimal design. SODA 2018 (pp. 2240-2255) (link).
  11. (Michael D.) Nikolov, A., & Singh, M. (2016). Maximizing determinants under partition constraints. STOC 2016 (pp. 192-201) (link).
  12. () Elbassioni, K., & Nguyen, T. T. (2017). Approximation algorithms for binary packing problems with quadratic constraints of low cp-rank decompositionsDiscrete Applied Mathematics230, 56-70 (link).
  13. (Christoph O.) Mai, T. & Vazirani, V. (2018). Finding Stable Matchings That Are Robust to Errors in the Input, ESA 2018 (pp. 60:1-60:11) (link).
  14. (Marcel M.) Brubach, B., Sankararaman, K. A., Srinivasan, A., & Xu, P. (2016). New algorithms, better bounds, and a novel model for online stochastic matching. ESA 2016 (link).
  15. () Manshadi, V. H., Gharan, S. O., & Saberi, A. (2012). Online stochastic matching: Online actions based on offline statisticsMathematics of Operations Research37(4), 559-573 (link)
  16. () Wang, X., Truong, V. A., & Bank, D. (2018). Online advance admission scheduling for services with customer preferencesarXiv preprint arXiv:1805.10412 (link).
  17. (Yujin C.) Grandoni, F., Leonardi, S., Sankowski, P., Schwiegelshohn, C., & Solomon, S. (2019). (1 + ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time, SODA 2019 (pp. 1886-1898) (link).
  18. (Michel R.) Buchbinder, N., Feldman, M., & Garg, M. (2018). Online submodular maximization: Beating 1/2 made simplearXiv preprint arXiv:1807.05529 (link).
  19. (Max Z.) Correa, J., Cristi, A., & Oosterwijk, T. (2019). On the Price of Anarchy for Flows over Time.



Schedule of Talks

Schedule (Room: MA 313)
Thursday, June 13
Rolf W.
Convex Programming for Scheduling Unrelated Parallel Machines
Yvonne M.
Unrelated Machine scheduling for Jobs with Uniform Smith Ratios
Lukas S.
Stochastic Load Balancing on Unrelated Machines
Rick G.
Greed works - Online Algorithms for Unrelated Machine Stochastic Scheduling
«Graph Algorithms»
Thursday, June 13
Minh P.
A simpler and faster Strongly Polynomial Algorithm for Generalized Flow Maximization
Tim G.
Expander Flows, Geometric Embeddings and Graph Partitioning
Elaine Z.
Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics
Max Z.
On the Price of Anarchy for Flows over Time

«Searching and Matching»
Friday, June 14
Hannes R.
Searching a Tree with Permanently Noisy Advice
Christoph O.
Finding Stable Matchings That are Robust to Errors in the Input
Marcel M.
New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching
Yujin C.
(1+ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time
«Approximation Algorithms»
Friday, June 14
Sebastian O.
Approximate Positive Correlated Distributions and Approximation Algorithms for D-Optimal Designs
Michael D.
Maximizing Determinants under Partition Constraints
Armin F.
Selfish Knapsack
Michael R.
Online Submodular Maximization: Beating 1/2 Made Simple



Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe

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