#
Monday Lecture and Colloquium

**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**

### Volker Kaibel -
Otto-von-Guericke-Universität Magdeburg

###
Which Matrices are Slack Matrices of Polytopes?

*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**

### Yann Disser -
Technische Universität Berlin

### Knapsack with Unknown Capacity

*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.

Letzte Aktualisierung:
12.04.2013