BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//CERN//INDICO//EN
BEGIN:VEVENT
SUMMARY:12th Colloquium of Research Area C3 [C3 Kolloquium / Colloquium of
  the Research Area C3]
DTSTART:20260305T080000Z
DTEND:20260305T103000Z
DTSTAMP:20260308T034400Z
UID:indico-event-1132@math-events.uni-bonn.de
DESCRIPTION:Speakers: André Nusser (Université Côte d’Azur\, CNRS\, I
 nria\, France)\, Antonia Ellerbrock (University of Bonn)\n\n09:00 - 09:30
       Coffee and Tea (2nd floor\, Lounge)\n09:30 – 10:15     Ant
 onia Ellerbrock: An Efficient Algorithm for Minimizing Ordered Norms in Fr
 actional Load Balancing\n10:15 – 10:45    Coffee break (2nd floor\, Lo
 unge)\n10:45 – 11:30    André Nusser: Lower bounds in computational 
 geometry\n \nAntonia Ellerbrock: An Efficient Algorithm for Minimizing Or
 dered Norms in Fractional Load BalancingWe study the problem of minimizing
  an ordered norm of a load vector over d resources\, where n customers con
 tribute to the load of each resource with a solution from a customer-speci
 fic convex set. We devise an efficient randomized (1+ε)-approximate algor
 ithm. With high probability\, it calls given oracles that minimize linear 
 functions (with non-negative coefficients) over the customer sets only lin
 early often (in n and d\; up to log-factors). In the worst case\, we are s
 lower by a factor of n.While this result has been known for the maximum no
 rm 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 throu
 ghout 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 gu
 arantee sufficient expected progress and bound the total number of oracle 
 calls linearly (up to log-factors) with high probability.Our algorithm use
 s a resource price mechanism motivated by the follow-the-regularized-leade
 r paradigm\, and expressed by smooth approximations of ordered norms. We n
 eed and show that these have non-trivial stability properties\, which may 
 be of independent interest.This is joint work with Daniel Blankenburg\, Th
 omas Kesselheim\, and Jens Vygen.\n \nAndré Nusser: Lower bounds in comp
 utational geometry\nIn this talk we consider a diverse set of lower bounds
  for problems in computational geometry. To that end\, we briefly review s
 ome core conjectures in fine-grained complexity theory and then show elega
 nt reductions to fundamental problems in computational geometry\, explaini
 ng their intricacy. We then turn to an unconditional lower bound for the u
 nion volume estimation problem\, proving tightness of a classical sampling
  algorithm by Karp\, Luby\, and Madras for this problem.\n \n \n \n\nht
 tps://math-events.uni-bonn.de/event/1132/
LOCATION:Arithmeum\, Lennéstr.\,  2 - Seminarraum (Arithmeum / Research I
 nstitute for Discrete Mathematics)
URL:https://math-events.uni-bonn.de/event/1132/
END:VEVENT
END:VCALENDAR