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

Dr. Torsten Mütze, Dr. Guillaume Sagnol

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 (sagnol@math.tu-berlin.de).

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.

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 Scheduling. arXiv 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 partitioning. Journal 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 decompositions. Discrete Applied Mathematics, 230, 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 statistics. Mathematics of Operations Research, 37(4), 559-573 (link)
16. () Wang, X., Truong, V. A., & Bank, D. (2018). Online advance admission scheduling for services with customer preferences. arXiv 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 simple. arXiv preprint arXiv:1807.05529 (link).
19. (Max Z.) Correa, J., Cristi, A., & Oosterwijk, T. (2019). On the Price of Anarchy for Flows over Time.