Workshop: Continuous approaches to discrete optimization

Dates: October 11 - 15, 2021
Venue: HIM lecture hall (Poppelsdorfer Allee 45, Bonn)


Due to COVID-19, participation must be coupled with proof that each participant is either fully vaccinated, cured or tested negative on COVID. This procedure corresponds to the current hygienic regulations. On-site participation can therefore only be allowed to registered participants, who will be informed about the corresponding on-site procedure in due time. The workshop will be held as a hybrid event.

Organizers: Chandra Chekuri (Illinois), Daniel Dadush (Amsterdam), Yin Tat Lee (Washington), Stephen Wright (Wisconsin)

Description:
Spectacular recent advances have been made in the quest for faster algorithms for key combinatorial optimization problems, such as maximum flow and matching, by taking advantage of and improving upon tools in continuous optimization (e.g. fast LP solving via first-order & interior point methods). Continuous techniques have also been fundamental to advances in online problems in combinatorial optimization (e.g. primal-dual methods) such as online matching and the k-server problem. To make further progress, it has become clear that sophisticated combinations of these techniques with tools from approximate linear algebra, data-structures, graph theory, convex geometry and other areas will be required. The purpose of this workshop is to bring researchers in related areas together to stimulate collaboration and explore applications of these techniques across optimization, from both a theoretical and practical perspective.

 

You can find the abstract here.

You can find the schedule here.

Video recordings:

Day 1

Jan Van den Brand: From Interior Point Methods to Data Structures and back

Rasmus Kyng: A numerical analysis approach to convex optimization

Yang Liu: Fully Dynamic Electrical Flows: Sparse Maxflow Faster than Goldberg-Rao

Debmalya Panigrahi: Isolating Cuts: A New Tool for Minimum Cut Algorithms

Sorrachai Yingchareonthawornchai: Approximating k-Edge-Connected Spanning Subgraphs via a Fast Linear Program Solver

Kent Quanrud: On Iterative Peeling and Supermodularity for Densest Subgraph

 

 

Day 2

Sally Dong: Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear Time

Bento Natura: Fast Exact Solvers for Linear Programs via Interior Point Methods

Jacek Gondzio: Applying interior point algorithms in column generation and cuttingplane methods

Andrea Lodi: Cutting Plane Generation Through Sparse Principal Component Analysis

Jens Vygen: Continuous approaches to VLSI routing

Robert Luce: Solving nonconvex quadratic optimization problems with Gurobi

Aaron Sidford: Unit Capacity Maximum Flow in Almost m^(4/3) Time

Day 3

Rico Zenklusen, Vera Traub: Bridging the Gap Between Tree and Connectivity Augmentation: Unified and Stronger Approaches

Matthias Mnich: Approximation Algorithms for Hard Cut Problems via Continuous Relaxations

Sebastian Pokutta: A distributed accelerated algorithm for the 1-fair packing problem

Stefan Weltge: Speeding up the Cutting Plane Method?

Zhao Song: Fast Iterative Algorithm via Nearest/Furthest Neighbor Search

Alina Ene: Adaptive gradient descent methods for constrained optimization

Jelena Diakonikolas: Local Acceleration of Frank-Wolfe Methods

Day 4

Roie Levin: Random Order Set Cover is as Easy as Offline

Gerard Cornuejols: Dyadic linear programming

Ola Svensson: Learning-Augmented Online Algorithms and the Primal-Dual Method

Anupam Gupta: Covering LP Relaxations for k-Server

Sebastian Bubeck: Chasing small sets

Day 5

Haotian Jiang: Minimizing Convex Functions with Integral Minimizers

Deeparnab Chakrabarty: Polynomial Lower Bounds for Parallel Submodular Function Minimization