 ## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, September 13, 2012, 12:15 pm

Duration: 30 minutes

Location: NO C44

Speaker: Friedrich Eisenbrand (EPFL)

## Subdeterminants and the Diameter of Polyhedra

We derive a new upper bound on the diameter of a polyhedron P = {x \in R^n : Ax ≤ b}, where A \in Z^{m \times n}. The bound is polynomial in n and the largest absolute value of a sub-determinant of A, denoted by \Delta. More precisely, we show that the diameter of P is bounded by O(\Delta^2 n^4 log(n\Delta)). If P is bounded, then we show that the diameter of P is at most O(\Delta^2 n^3.5 log (n\Delta)).

For the special case in which A is a totally unimodular matrix, the bounds are O(n^4 log n) and O(n^3.5 log n) respectively. This improves over the previous best bound of O(m^16 n^3 (log mn)^3) due to Dyer and Frieze.

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks