Raine Heck: Colorful vector balancing |
||||
|
||||
|
||||
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/8990 |
JEvents v3.1.8 Stable Copyright © 2006-2013