The ACO Seminar (2013–2014)

This is a joint work with Imre Bárány and Emmanuel Livshits. Given a sequence A=(a₁,...,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₁,...,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.