Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department |
Algorithms, Combinatorics and Optimization Seminar
For more information, please visit the home page for the program in Algorithms, Combinatorics and Optimization at Carnegie Mellon University. Carnegie Mellon University offers an interdisciplinary Ph.D program in Algorithms, Combinatorics and Optimization. This program is the first of its kind in the United States. It is administered jointly by the Tepper School of Business (Operations Research group), the Computer Science Department (Algorithms and Complexity group) and the Department of Mathematical Sciences (Discrete Mathematics group). (Learn more...) 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_{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 |