Vera Traub - Research Institute for Discrete Mathematics University Bonn

On the Bidirected Cut Relaxation for Steiner Tree and Steiner Forest

The Steiner Tree problem is one of the most prominent network design problems. It asks to connect a given set of terminals in the cheapest possible way. A promising ingredient for the design of fast and accurate approximation algorithms is the bidirected cut relaxation (BCR). We prove that this linear programming relaxation has integrality gap less than 2.

We also consider the Steiner Forest problem, an important generalization of Steiner Tree. The current best approximation factor for Steiner Forest is 2 and improving on this factor is a major open problem in the area of approximation algorithms. We describe an natural extension of BCR to Steiner Forest and prove that it has several promising properties.

This is joint work with Jarek Byrka and Fabrizio Grandoni.

Daniel Dadush - Department of Mathematics Utrecht University

Strongly Polynomial Frame Scaling to High Precision

The frame scaling problem is: given vectors U = {u_1, ..., u_n}  in  R^d, positive marginals c in R^n, and precision epsilon > 0, find left and right scalings L in R^{d x d}, r in R^n such that (v_1,\dots,v_n) := (Lu_1 r_1,\dots,Lu_nr_n) simultaneously satisfies sum_{i=1}^n v_i v_i^T = I_d and |v_j|_2^2 = c_j, for all j in [n], up to error \epsilon. This problem has appeared in a variety of fields throughout linear algebra and computer science. In this work, we give a strongly polynomial algorithm for frame scaling with \log(1/epsilon) convergence.

This answers a question of Diakonikolas, Tzamos and Kane (STOC 2023), who gave the first strongly polynomial randomized algorithm with poly(1/epsilon) convergence for Forster transformation, the special case c = (d/n) 1_n. 
Our algorithm is deterministic, applies for general marginals c, and requires O(n^3 log(n/epsilon)) iterations as compared to the O(n^5 d^11/epsilon^5) iterations of DTK.
By lifting the framework of Linial, Samorodnitsky and Wigderson (Combinatorica 2000) for matrix scaling to the frame setting, we are able to simplify both the algorithm and analysis. 
Our main technical contribution is to generalize the potential analysis of LSW  to the frame setting and compute an update step in strongly polynomial time that achieves geometric progress in each iteration. 
In fact, we can adapt our results to give an improved analysis of strongly polynomial matrix scaling, reducing the $O(n^5 log(n/epsilon)) iteration bound of LSW to O(n^3 \log(n/epsilon)). 
Additionally, we prove a novel bound on the size of approximate frame scaling solutions, involving the condition measure \bar\chi studied in the linear programming literature, which may be of independent interest.

 This is joint work with Akshay Ramachandran.

Hannaneh Akrami - TRA Modelling

Epistemic EFX Allocations Exist for Monotone Valuations

We study the fundamental problem of fairly dividing a set of indivisible items among agents with (general) monotone valuations. The notion of envy-freeness up to any item (EFX) is considered to be one of the most fascinating fairness concepts in this line of work. Unfortunately, despite significant efforts, existence of EFX allocations is a major open problem in fair division, thereby making the study of approximations and relaxations of EFX a natural line of research. Recently, Caragiannis et al. introduced a promising relaxation of EFX, called epistemic EFX (EEFX). We say an allocation to be EEFX if, for every agent, it is possible to shuffle the items in the remaining bundles so that she becomes "EFX-satisfied". Caragiannis et al. prove existence and polynomial-time computability of EEFX allocations for additive valuations. A natural question asks what happens when we consider valuations more general than additive?

We address this question and answer it affirmatively by establishing the existence of EEFX allocations for an arbitrary number of agents with general monotone valuations. To the best of our knowledge, beside EF1, EEFX is the only known relaxation of EFX to have such strong existential guarantees. Furthermore, we complement our existential result by proving computational and information-theoretic lower bounds. We prove that even for an arbitrary number of (more than one) agents with identical submodular valuations, it is PLS-hard to compute EEFX allocations and it requires exponentially-many value queries to do so. This is joint work with Nidhi Rathi.

László Végh - Hertz Chair at TRA  Modelling

Inauguration lecture: The Discrete and Continuous sides of Linear Optimization 

Linear optimization has been at the heart of optimization for more than sixty years. Besides its immense modelling capabilities and practical impact, the pursuit of more efficient linear optimization algorithms has been a driving force in the theory of optimization, due to its dual nature as a discrete and continuous problem. The talk will highlight classical and more recent developments in the theory of linear optimization, highlighting the connections to discrete mathematics, analysis, and geometry.