### 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 aquire important skills for presenting these technical results to a wider audience.

The number of participants to the seminar is strictly limited to 16. We indicate another related seminar on Variants of Shortest Path Problems taking place at ZIB.

### 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 III course).

### Talk schedule

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

Thursday | Friday |
---|---|

09:00 Paper 15 (Mathias L.) | 09:00 Paper 2 (Simon W.) |

09:45 Paper 17 (Norman H.) | 09:45 Paper 3 (Flora E.) |

10:30 Paper 13 (Michelle L. D.) | 10:30 Paper 7 (Alexandra M.) |

11:15 Paper 14 (Paula B.) | 11:15 Paper 16 (Antonia A.) |

13:30 Paper 8 (Bryan N.) | 13:30 Paper 18 (Marie S. E.) |

14:15 Paper 11 (Alicia B.) | 14:15 Paper 19 (Jonas I.) |

15:00 Paper 12 (Rick G.) |

### Important dates

The first meeting will take place on **April 16, 2018, 10:15**, in room **MA 544.**

The second meeting where papers are assigned to students and general guidelines are discussed will take place on **April 23, 2018, 10: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.

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

### List of papers

- J. de Loera and S. Onn,
**3-Way transportation programs are universal**, SIAM Journal on Optimization 17(3):806-821, 2006 (link) *(Simon W.)*R. Hemmecke, S. Onn, and R. Weismantel,**N-fold integer programming and nonlinear multi-transshipment**, Optimization Letters 5:13–25, 2011 (link).*(Flora E.)*L. Fleisher, M. Goemans, V. Mirrokni, and M. Sviridenko,**Tight approximation algorithms for maximum general assignment problems**, SODA 2006 (pp. 611-620), 2006 (link).- R.D. Carr, L. Fleischer, V.J. Leung, and C.A. Phillips,
**Strengthening integrality gaps for capacitated network design and covering problems**, SODA 2000 (pp. 106-115), 2000 (link). - S.G. Kolliopoulos and N.E. Young,
**Approximation algorithms for covering/packing integer programs**, Journal of Computer and System Sciences, 71(4), 495-505, 2005 (link). *(Ivan S.)*N. Bansal and K. Pruhs,**The geometry of scheduling**, SIAM Journal on Computing 43(5):1684–1698, 2014 (link).*(Alexandra M.)*S. Dasgupta,**A cost function for similarity-based hierarchical clustering**, STOC 2016 (pp. 118-127), 2016 (link).*(Bryan N.)*S. Alstrup, A. Georgakopoulos, E. Rotenberg, and C. Thomassen,**A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time**, SODA 2018 (pp. 1645-1649), 2018 (link)- K. Jansen, K.-M. Klein, and J. Verschae,
**Closing the gap for makespan scheduling via sparsification techniques**, ICALP 2016 (pp. 72:1–72:13), 2016 (link). *(Christopher D.)*J. Paat, R. Weismantel, and S. Weltge,**Distances of optimal solutions of mixed-integer programs**, arXiv preprint 1801.08751, 2018 (link).*(Alicia B.)*N. Bansal and M. Sviridenko,**The Santa Claus problem**, STOC 2006 (pp. 31-40), 2006 (link).*(Rick G.)*T. Ebenlendr, M. Krcal, and J. Sgall,**Graph balancing: a special case of scheduling unrelated parallel machines**, Algorithmica 68:62–80, 2014 (link).*(Michelle L. D.)*J. Sawada and A. Williams,**Greedy flipping of pancakes and burnt pancakes**, Discrete Applied Mathematics 210:61-74, 2016 (link).*(Paula B.)*J. Sawada and A. Williams,**A Hamilton path for the sigma-tau problem**, SODA 2018 (pp. 568-575), 2018 (link).*(Mathias L.)*D. Gonçalves, L. Isenmann, and C. Pennarun,**Planar graphs as L-intersection or L-contact graphs**, SODA 2018 (pp. 172-184), 2018 (link).*(Antonia A.)*O. Svensson, J. Tarnawski, L. A. Végh,**A constant-factor approximation algorithm for the asymmetric traveling salesman problem**, STOC 2018 (link).*(Norman H.)*T.M. Chan,**Tree drawings revisited**, SoCG 2018 (link).*(Marie S. E.)*M. Macko, K. Larson, L. Steskal,**Braess's Paradox for Flows over Time**, Theory of Computing Systems (pp. 86-106), 2013 (link).*(Jonas I.)*U. Bhaskar, L. Fleischer, and E. Anshelevich,**A Stackelberg Strategy for Routing Flow over Time**, Games and Economic Behavior (pp. 232-247), 2015 (link).