Bernoulli Center Summer School on Modern Trends in Combinatorial Optimization

July 18 – 22, 2022, EPFL, Bernoulli Center, Switzerland

The Bernoulli Center summer school “Modern Trends in Combinatorial Optimization is a summer school orginized at EPFL.
The goal of the summer school is to discuss modern trends and exciting recent results in Combinatorial Optimization.
This summer school is part the Bernoulli Center program on Combinatorial Optimization.

Speakers:

• Danupon Nanongkai (University of Copenhagen, MPI-INF Saarbrücken, and KTH)
• Vera Traub (ETH Zürich)
• Luca Trevisan (Bocconi University, Milano)
• Santosh Vempala (Georgia Tech)
  
  

Program and Material:

• Danupon Nanongkai: Efficient graph algorithms across computing paradigms (TA: Alexandra Lassota)
  
  There have been many fast algorithms discovered recently for graph
  problems that otherwise witnessed no progress in the last few decades. 
  In this lecture series, we will explore some of the techniques
  underlying these advances. The focus will on
  (1) graph decomposition techniques, especially the low-diameter
  decomposition technique and its recent application to single-source
  shortest paths on graphs with negative weights, and
  (2) the isolating cut technique that allows us to solve hard graph
  problems (e.g. vertex connectivity and Gomory-Hu tree) using fast
  max-flow computation.
  While the lectures will focus on sequential algorithms, we will also
  discuss applications of these techniques in other settings such as
  distributed and dynamic algorithms. (In fact, these settings were where some of these techniques originated from.)
  
  Lecture material: Part 1, Part 2, Part2.1 .
  Exercise: Problemset (For Monday, 18.07., focus on Problems 1 and 2, Problem 3 is optional)
  
  
  
• Vera Traub: Approximation Algorithms for Network Design Problems (TA: Etienne Bamas)
  
  The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. A celebrated result by Jain [Combinatorica, 2001] provides a 2-approximation algorithm for a wide class of these problems. However, even for many very basic special cases nothing better is known. In this lecture series we present some of the techniques underlying recent advances in this area.

  We show how these techniques can be applied to two different network design problems. First, we consider the weighted tree augmentation problem, which is one of the most intensely studied augmentation problems. It asks for the cheapest way to increase the edge-connectivity of a graph from 1 to 2 by adding edges among a given set of options. Second, we discuss the Steiner tree problem, which asks for the cheapest way to connect a given set of terminals in a weighted graph.

  
  Exercise: Exercise1and2

  Related material: https://arxiv.org/pdf/2104.07114.pdf 
  and https://arxiv.org/pdf/2107.07403.pdf 

  
  
  
• Luca Trevisan: Analysis of graph algorithms in random and semi-random generative models (TA: Adam Polak)
  
  
  We will study the use of techniques from linear algebra and from convex optimization to solve graph problems where the graph is sampled from a random or a semi-random generative model. A “semi-random” generative model is one intermediate between worst-case and average-case, where the graph is generated with a combination of random choices and adversarial choices.
  We will see how to apply spectral (i.e. linear-algebraic) techniques to find a planted clique or planted independent set in a random graph, and to discover communities in the “stochastic block model” of random networks. We will then see how to apply semidefinite programming (a convex optimization methodology that generalizes both linear programming and certain spectral methods) to both problems, and study how it performs in semi-random variants of the planted clique model and of the stochastic block model.
  
  Webpage for the lecture can be found here.
  Exercise material: Problem Set 1, Problem Set 2
  Reading material can be found here.
  
  
• Santosh Vempala: The Interplay between Sampling and Optimization in High Dimension (TA: Sai Ganesh)
  
  Sampling and Optimization are two fundamental problems in high dimension. In this short course, we will discuss algorithms for them focusing on connections and parallels between the two problems. After an introduction to useful properties of convexity and logconcavity, we will see (1) how to reduce optimization to sampling with cutting planes (2) simulated annealing and its duality with the interior-point method (3) efficient sampling algorithms, in particular, the ball walk, Dikin walk and Riemannian Hamiltonian Monte Carlo (4) extensions beyond convexity and, time permitting, (5) Langevin diffusion as gradient descent.
  
  Lecture notes and exercises can be found here.
  For extra reading material, click here or follow these links:
  1) https://faculty.cc.gatech.edu/~vempala/papers/logcon.pdf
  2) https://arxiv.org/abs/1807.03465
  3) https://drops.dagstuhl.de/opus/volltexte/2022/16345/pdf/LIPIcs-ICALP-2022-4.pdf

Schedule:

Venue:

All lectures take place in BCH 2201,
the coffee breaks take place in the third floor of the GA building.

During the exercises, Bernoulli offers some nice rooms. The lecturer and TAs can be found in their offices in case of questions. 

For easy navigation, use plan.epfl.ch and search for “BCH 2201” or “GA”, respectively. 

Participants:

Abhiruk Lahiri
Adam Polak
Afrouz Jabal Ameli
Akash Kumar
Alantha Newman
Ali Parviz
Amir Nikabadi
Anastasiia Kucherenko
Andrea Gilot
Arghya Chakraborty
Ashutosh Shankar
Benjamin Aram Berendsohn
Bento Natura
Charilaos Pipis
Christian Nöbel
Christoph Hunkenschröder
Daniel Dadush
Danupon Na Nongkai
Davide Mazzali
Diba Hashemi
Dürr Anita
Dylan Hyatt-Denesik
Eleonore Bach
Emanuele CONCAS
Etienne Bamas
Eva Maria Gonzalez
Felix Klingelhoefer
Filippos Christodoulou
Gabriel Morete de Azevedo
Golnoosh Shahkarami
Ivan Sergeev
Jana Cslovjecsek
Janina Reuter
Jari de Kroon
Jiaye Wei
Joachim Spoerhase
Joakim Blikstad
Kasper Lindberg
Kirill Kukharenko
Lasse Wulf
Leander Schnaars
Leo Krull
Loay Mualem
Lorenzo Ciardo
Marina Drygala
Martina Gallato
Mateusz Wasylkiewicz
Matin Ansaripour
Matthieu Haeberle
Meike Neuwohner
Miguel Bosch Calvo
Mikele Gajda
Mikhail Makarov
Ming Ding
Minh Hieu NGUYEN
Minh Tam Tran
Mohadese Ghafari
Mohamad Fakhouri
Mohsen Nafar
Moritz Buchem
Moritz Venzin
Nick Fischer
Nicolas El Maalouly
Nikhil Kumar
Parinya Chalermsook
Pınar YUNUSOĞLU
Rodrigo Raya
Sai Ganesh Nagarajan
Samuel Thomas
Sander Borst
Sandip Banerjee
Sanjeev Khanna
Santosh Vempala
Sarah Ludwig
Sarah Morell
Sasha Voitovych
Shay Moran
Silvia Di Gregorio
Simon Meierhans
Sricharan AR
Tamás Schwarcz
Thiago Lima Oliveira
Tijn de Vos
Vera Traub
VO Thi Quynh Trang
Weiqiang Yuan
Xinrui Jia
Yiran Zhu
Yonggang Jiang
Zahra Parsaeian
Zhenyu Zhu
Zhile Jiang
ZHU Zhenyu
Zihang Wu
Ziyi Guan

How to apply:

The deadline for applications was 07.05.2022.

There is no registration fee.


Local Organizers:

• Friedrich Eisenbrand
• Alexandra Lassota
• Ola Svensson