Theory of Combinatorial Algorithms
Prof. Emo Welzl

 People Activity Report Previous Reports Research Mittagsseminar Teaching Workshops Social Activities Topics for Master / Bachelor Theses CGAL Geometric Algorithms Library
Mittagsseminar (in cooperation with A. Steger)

 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.

Previous talks by year:   2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996

Information for students and suggested topics for student talks