A Frankfurt-Darmstadt Afternoon on Discrete Mathematics

July 3, 2015, 16:00 s.t.

Goethe-Universität Frankfurt am Main, Campus Bockenheim

Robert-Mayer-Str. 10, Room 711 groß

To the main page of the meeting


Frank Vallentin (Universität zu Köln): New upper bounds for the density of translative packings of superspheres

In this talk I will present new upper bounds for the maximum density of translative packings of superspheres in three dimensions (unit balls for the $l^p$-norm). This will give some strong indications that the lattice packings experimentally found in 2009 by Jiao, Stillinger, and Torquato are indeed optimal among all translative packings. For this we apply the linear programming bound of Cohn and Elkies which originally was designed for the classical problem of packings of round spheres. The proof of our new upper bounds is computational and rigorous. Our main technical contribution is the use of invariant theory of pseudo-reflection groups in polynomial optimization. This is joint work with Maria Dostert, Cristóbal Guzmán, and Fernando Mário de Oliveira Filho.

Martin Skutella (TU Berlin): Unsplittable flows and the ring loading problem

We study flow problems in networks with given source-sink pairs and associated demand values. An unsplittable flow has to satisfy each demand along a single source-sink path. The latter restriction turns otherwise efficiently solvable flow problems into NP-hard ones. If all demands share a common source node, Dinitz, Garg, and Goemans showed that any fractional flow can be turned into an unsplittable flow while increasing the flow on any edge by at most the maximum demand value $d_{\max}$. It is an open problem whether this result can be generalized to the setting of min-cost (unsplittable) flows ("Goeman's Conjecture"). A seemingly related conjecture by Schrijver, Seymour, and Winkler claimed that the integrality gap of the ring loading problem (unsplittable flow problem on ring networks) is at most $d_{\max}$. We present some more as well as some less recent progress on these conjectures.