TU Berlin

FG Kombinatorische Optimierung und GraphenalgorithmenSeminar: Seminar on Graphs, Algorithms and Optimization

COGA 5-Wheel

Inhalt des Dokuments

zur Navigation

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.

Prerequisites

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)
SESSION 1
«Scheduling»
Thursday, June 13
Student
Paper
09:15-09:55
Rolf W.
Convex Programming for Scheduling Unrelated Parallel Machines
10:00-10:40
Yvonne M.
Unrelated Machine scheduling for Jobs with Uniform Smith Ratios
10:45-11:25
Lukas S.
Stochastic Load Balancing on Unrelated Machines
11:30-12:10
Rick G.
Greed works - Online Algorithms for Unrelated Machine Stochastic Scheduling
SESSION 2
 
«Graph Algorithms»
Thursday, June 13
Student
Paper
13:05-13:45
Minh P.
A simpler and faster Strongly Polynomial Algorithm for Generalized Flow Maximization
13:50-14:30
Tim G.
Expander Flows, Geometric Embeddings and Graph Partitioning
14:35-15:15
Elaine Z.
Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics
15:20-16:00
Max Z.
On the Price of Anarchy for Flows over Time
SESSION 3


«Searching and Matching»
Friday, June 14
Student
Paper
09:15-09:55
Hannes R.
Searching a Tree with Permanently Noisy Advice
10:00-10:40
Christoph O.
Finding Stable Matchings That are Robust to Errors in the Input
10:45-11:25
Marcel M.
New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching
11:30-12:10
Yujin C.
(1+ε)-Approximate Incremental Matching in Constant Deterministic Amortized Time
SESSION 4
«Approximation Algorithms»
Friday, June 14
Student
Paper
13:05-13:45
Sebastian O.
Approximate Positive Correlated Distributions and Approximation Algorithms for D-Optimal Designs
13:50-14:30
Michael D.
Maximizing Determinants under Partition Constraints
14:35-15:15
Armin F.
Selfish Knapsack
15:20-16:00
Michael R.
Online Submodular Maximization: Beating 1/2 Made Simple

 

 

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe