Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Description

The Vector Partition Problem concerns the partitioning of a set of $n$ vectors in $d$-space into $p$ parts so as to maximize a suitable convex objective function. It has broad expressive power and arises in a variety of areas ranging from economics to symbolic computation. The problem can be treated through the maximization over suitable Partition Polytopes in $d\times p$ matrix space, and its computational complexity is intimately related to the vertex complexity of such polytopes. I will describe recent polynomial upper and lower bounds on the complexity based on the introduction of the class of Momentopes, on certain polynomial realizations of Davenport-Schinzel sequences, and on suitable Zonotopal refinements of partition polytopes. One application, to be presented elsewhen, is a polynomial time algorithm for computing Universal Grobner bases of point configurations in fixed dimension