Monday, April 29, 2013
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
Slack matrices of polytopes have recently played an increasingly important role in polyhedral combinatorics, as the nonnegative rank of a slack matrix of a polytope equals its extension complexity. Here, the nonnegative rank of a nonnegative matrix is the smallest size of a nonnegative factorization (similar to the usual rank being the smallest size of any factorization), and the extension complexity of a polytope P is the smallest number of facets of any polytope as whose projection P can be obtained. In this lecture, we first introduce the notion of extended formulations by presenting some examples and highlight the connection between the extension complexity of a polytope and the nonnegative rank of its slack matrix. In the second part, which is based on joint work with J. Gouveia, R. Grappe, K. Pashkovich, R. Richardson, and R. Thomas, we provide two characterizations of slack matrices. In particular, we show that the algorithmic problem to decide whether a matrix is a slack matrix is polynomial time equivalent to the vertex enumeration problem.
Colloquium - 16:00
Abstract:
We consider the classical knapsack problem with the twist that we do not know the capacity of the knapsack a priori. Once an item is put into the knapsack, it cannot be taken out again, and whenever an item doesn't fit, we may discard the item and continue to fill the knapsack with the remaining items. Our goal is to put the items into a universal order, such that trying to pack the items in this order gives a good solution for every capacity. We give an algorithm that produces an ordering that always achieves a 2-approximation of the optimum solution. We show that this algorithm is best-possible in the sense that for some instances no ordering can achieve a better ratio.