Seminar on Graphs, Algorithms and Robust Optimization

In this seminar we cover various aspects of algorithmic problems on graphs and related combinatorial structures. A special focus will be on robust optimization methods, which protect against data uncertainty. 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 purpose of this seminar is to read and understand recent results from the literature on graphs, algorithms and robust optimization. Participants are expected to have some experience with the analysis of advanced algorithms (e.g. from an ADM III course).

Dr. Torsten Mütze [1], Dr. Guillaume Sagnol [2]

The first meeting will take place on April 24, 2017, 10:15, in room MA 751.

The second meeting where papers are assigned to students and general guidelines are discussed will take place on May 08, 2017, 10:15, in room MA 751. 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 [3].

On May 15, 2017, 10:15, in room MA 751, Torsten and Guillaume will give a presentation of 30 minutes each, to give a live demonstration of superb presentation skills.

Each participant will give a 5-minute introductory presentation on May 22, 2017, 10:15, in room MA 751. Please send us the slides for the 5-minute presentation in PDF format beforehand by email (muetze@math.tu-berlin.de [4]).

A PDF version of the presentation slides has to be handed in before June 22, 2017 for a final check.

The seminar will be held as a block seminar on June 29 & 30, 2017, 10:00-19:00 in MA 212. All participants are expected to be present during all the talks.

Brief summary of papers 11-20 (pdf [5])

1. (Nils E.) C. A. Holzmann and F. Harary, On the tree graph of a matroid, SIAM Journal on Applied Mathematics 22(2), 187-193, 1972 (link [6])
2. (Hoang M. P.) V. L. Kompel'makher and V. Liskovets, Sequential generation of arrangements by means of a basis of transpositions, Cybernetics 11(3):362-366, 1975 (link [7])
3. (Niklas J.) F. Chung, P. Diaconis and R. Graham, Universal cycles for combinatorial structures, Discrete Mathematics 110:43-59, 1992 (link [8])
4. (Oliver K.) J. R. Johnson, Universal cycles for permutations, Discrete Mathematics 309(17): 5264-5270, 2009 (link [9])
5. (Henriette F.) F. Hurtado and M. Noy, Graph of triangulations of a convex polygon and tree of triangulations, Computational Geometry 13(3), 179-188, 1999 (link [10])
6. (Martin F.) O. Aichholzer, F. Aurenhammer, C. Huemer and B. Vogtenhuber, Gray code enumeration of plane straight-line graphs, Graphs and Combinatorics 23(5), 467-479, 2007 (link [11])
7. (Berenike M.) G. Bhat and C. Savage, Balanced Gray Codes, Electronic Journal of Combinatorics 3(1), Research Paper #R25, 1996 (link [12])
8. (Thomas N.) F. Ruskey, J. Sawada and A. Williams, Binary bubble languages and cool-lex order, Journal of Combinatorial Theory, Series A 119(1), 155-169, 2012 (link [13])
9. (Daniel K.) B. Stevens and A. Williams, The Coolest Way to Generate Binary Strings, Theory of Computing Systems 54(4):551-577, 2014 (link [14])
10. (Leonie K.) R. Wua, J. Chang, H. Chan and K. Pai, A loopless algorithm for generating multiple binary tree sequences simultaneously, Theoretical Computer Science 556:25-33, 2014 (link [15])
11. (Michel S.) H. Hu and R. Sotirov, Special cases of the quadratic shortest path problem, preprint, 2016 (link [16])
12. (Sebastian O.) A. Pessoa, L. Di Puglia Pugliese, F. Guerriero and M. Poss, Robust constrained shortest path problems under budgeted uncertainty, Networks 66(2):98-111, 2014. (link [17])
13. (Thomas S.) M. Bougeret, A. Pessoa and M. Poss, Robust scheduling with budgeted uncertainty, preprint, 2016 (link [18])
14. (Sven F.) A. Agra, M. Santos, D. Nace and M. Poss, A dynamic programming approach for a class of robust optimization problems, SIAM Journal on Optimization, 26(3):1799-1823, 2016. (link [19])
15. (Kaja W.) H. Saran and V. Vazirani, Finding k cuts within twice the optimal. SIAM Journal on Computing, 24(1), 101-108, 1995. (link [20])
16. (Samuel M.) I. Ashlagi, P. Jaillet, V. Manshadi and M. Rees, Kidney Exchange in dynamic sparse heterogenous pools, preprint, 2014. (link [21])
17. (Benjamin M.) C. Buchheim and J. Kurtz, Min–max–min robust combinatorial optimization subject to discrete uncertainty. epub ahead of print, Mathematical Programming, 2016. (link [22])
18. (Geraldine F.) L. Castelli, M. Labbé and A. Violin, Network pricing problem with unit toll, Networks, 69(1):83-93, 2016. (link [23])
19. (Daniel B.) D. Bertsimas and A. Thiele, A robust optimization approach to inventory theory,  Operations Research, 54(1), 150-168, 2006. (link [24])
20. (Ansgar R.) S. Agrawal, Y. Ding, A. Saberi and Y. Ye, Price of correlations in stochastic optimization, Operations Research, 60(1), 150-162, 2012. (link [25])