Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni |
Algorithms, Combinatorics and Optimization Seminar
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_{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. Date: Thursday, February 6, 2014 Time: 3:30 pm Location: Wean Hall 8220 Submitted by: Boris Bukh |