Feb. 6, 3:30pm, Wean 8220

Victor Grinberg,

Block Partitions of Sequences

Victor Grinberg,

Block Partitions of Sequences

Abstract:

This is a joint work with Imre Bárány and Emmanuel Livshits.
Given a sequence *A*=(*a*_{1},...,*a*_{n}) of real numbers, a block *B* of the *A* is either a set *B*={*a*_{i},...,*a*_{j}} where *i*≤*j*
or the empty set. The size *b* of a block *B* is the sum of its elements. We show that when *0*≤*a*_{i}≤*1* and *k* is a
positive integer, there is a partition of *A* into *k* blocks *B*_{1},...,*B*_{k} with |*b*_{i}-*b*_{j}|≤*1* for every *i*, *j*. We extend this result in many directions. We also present polynomial algorithms for finding optimal (in various senses) block partitions.