CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
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=(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.

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