12th Colloquium of Research Area C3C3 Kolloquium / Colloquium of the Research Area C3

by André Nusser, Antonia Ellerbrock (University of Bonn)

Thursday Mar 5, 2026, 9:00 AM → 11:30 AM Europe/Berlin

Arithmeum, Lennéstr., 2 - Seminarraum (Arithmeum / Research Institute for Discrete Mathematics)

09:00 - 09:30      Coffee and Tea (2^nd floor, Lounge)

09:30 – 10:15    Antonia Ellerbrock: An Efficient Algorithm for Minimizing Ordered Norms in Fractional Load Balancing

10:15 – 10:45    Coffee break (2^nd floor, Lounge)

10:45 – 11:30    André Nusser: Lower bounds in computational geometry

 

Antonia Ellerbrock: An Efficient Algorithm for Minimizing Ordered Norms in Fractional Load Balancing

We study the problem of minimizing an ordered norm of a load vector over d resources, where n customers contribute to the load of each resource with a solution from a customer-specific convex set. We devise an efficient randomized (1+ε)-approximate algorithm. With high probability, it calls given oracles that minimize linear functions (with non-negative coefficients) over the customer sets only linearly often (in n and d; up to log-factors). In the worst case, we are slower by a factor of n.

While this result has been known for the maximum norm via the Multiplicative Weight Update method, existing proof techniques do not extend to arbitrary ordered norms. To close this gap, we need new techniques such as dynamic cost budgets per customer, which evolve throughout the algorithm and determine the allowed step sizes towards the final solution. The order in which we call our single-customer oracles to find the next partial solution is determined by non-uniform sampling. We can guarantee sufficient expected progress and bound the total number of oracle calls linearly (up to log-factors) with high probability.

Our algorithm uses a resource price mechanism motivated by the follow-the-regularized-leader paradigm, and expressed by smooth approximations of ordered norms. We need and show that these have non-trivial stability properties, which may be of independent interest.

This is joint work with Daniel Blankenburg, Thomas Kesselheim, and Jens Vygen.

 

André Nusser: Lower bounds in computational geometry

In this talk we consider a diverse set of lower bounds for problems in computational geometry. To that end, we briefly review some core conjectures in fine-grained complexity theory and then show elegant reductions to fundamental problems in computational geometry, explaining their intricacy. We then turn to an unconditional lower bound for the union volume estimation problem, proving tightness of a classical sampling algorithm by Karp, Luby, and Madras for this problem.