Év szerint Hónap szerint Ugrás a hónaphoz

Raine Heck: Colorful vector balancing

 iCal fájl letöltése
Csütörtök, 16. Február 2023, 12:30 - 14:00
The vector balancing problem, in which one is given a
collection of vectors in a d-dimensional unit norm ball and selects
signs {-1,+1} so that the norm of the signed sum of the vectors becomes
minimal, has been studied extensively for both general and specific
norms.  Answering a question originally posed by Barany and Grinberg in
1981, we extend results for both the Euclidean norm and the maximum norm
to a colorful setting. In this setting one is given color classes of
vectors in the unit ball of a norm on R^d, with the condition that 0 is
contained in the Minkowski sum of the convex hulls of  the color
classes. The goal is to select one vector of each color so that the norm
of the sum of the selected vectors is as small, i.e. uniformly bounded
from above. For the Euclidean norm, we use linear algebraic and
probabilistic techniques to prove that there is always a selection of
vectors whose sum has Euclidean norm at most \sqrt(d). For the maximum
norm we use a random walk algorithm to prove the asymptotically optimal
upper bound O(\sqrt(d)). These estimates agree with the ones for the
original vector balancing problem, and as such, are known to be
asymptotically optimal.
This is a joint work with Gergely Ambrus.
 
This lecture will be in the Riesz lecture room and will also be available on Zoom:
https://us06web.zoom.us/j/89905956522?pwd=R05YaVIwcWlna1FRam96VzBRbkhPQT09

Vissza

JEvents v3.1.8 Stable   Copyright © 2006-2013