Algorithms, Combinatorics and Optimization Seminar Victor Grinberg
Independent Scholar
Title: Block Partitions of Sequences

Abstract: 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.

Date: Thursday, February 6, 2014
Time: 3:30 pm
Location: Wean Hall 8220
Submitted by:  Boris Bukh