ACO The ACO Seminar (2013–2014)

Feb. 6, 3:30pm, Wean 8220
Victor Grinberg,
Block Partitions of Sequences


This is a joint work with Imre Bárány and Emmanuel Livshits. Given a sequence A=(a1,...,an) of real numbers, a block B of the A is either a set B={ai,...,aj} where ij or the empty set. The size b of a block B is the sum of its elements. We show that when 0ai1 and k is a positive integer, there is a partition of A into k blocks B1,...,Bk with |bi-bj|≤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.

Back to the ACO home page