The seminar will cover research papers in Algorithmics with a focus on Network Design and Optimization under Uncertainty, i.e. the question of finding good solutions under incomplete information. Please find a list of example topics below.

If you are interested in participating, please contact Daniel Schmidt before October 27thNovember 2nd. Places will be assigned shortly after that date.

Please see this website for instructions on how to connect to the university VPN and access literature remotely.

1. Aissi, Bazgan, and Vanderpooten. Min–Max and Min–Max Regret Versions of Combinatorial Optimization Problems: A Survey. European J. of Operational Research 197(2), 2009. (Link via Uni Bonn VPN).
2. Conde. On a Constant Factor Approximation for Minmax Regret Problems Using a Symmetry Point Scenario. European J. of Operational Research 219 (2), 2012. (Link via Uni Bonn VPN).
3. Kasperski and Zieliński. On the Existence of an FPTAS for Minmax Regret Combinatorial Optimization Problems with Interval Data. Operations Research Letters 35(4), 2007.
4. Gupta, Kumar, Pál, and Roughgarden. Approximation via Cost Sharing: Simpler and Better Approximation Algorithms for Network Design. J of the ACM 54(3). (Link via Uni Bonn VPN).
5. Fleischer, Könemann, Leonardi, and Schäfer. Simple Cost Sharing Schemes for Multicommodity Rent-or-Buy and Stochastic Steiner Tree. STOC 2006. (Link via Uni Bonn VPN).
6. Dhamdhere, Goyal, Ravi, Singh. How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems. FOCS 2005. (Preprint on author homepage).
7. Gupta, Nagarajan, and Vazirani. Thrifty Algorithms for Multistage Robust Optimization. IPCO 2005. (Link via Uni Bonn VPN) (Full version on arXiv)
8. Gupta, Pál, Ravi, and Sinha. What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization. APPROX/RANDOM 2005 2015. (Link via Uni Bonn VPN) (Full version via author homepage).
9. Gupta and Kumar. Greedy Algorithms for Steiner Forest. STOC 2015. (Link via Uni Bonn VPN).
10. Fiorini, Groß, Könemann, and Sanità. Approximating Weighted Tree Augmentation via Chvátal-Gomory Cuts. SODA 2018. (Link via Uni Bonn VPN).
11. Könemann, Olver, Pashkovich, Ravi, Swamy, and Vygen. On the Integrality Gap of the Prize-Collecting Steiner Forest LP. APPROX/RANDOM 2017. (Open Access Link)