Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Publication
Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
We derive a new upper bound on the diameter of a polyhedron , where . The bound is polynomial in and the largest absolute value of a sub-determinant of , denoted by . More precisely, we show that the diameter of is bounded by . If is bounded, then we show that the diameter of is at most . For the special case in which is a totally unimodular matrix, the bounds are and respectively. This improves over the previous best bound of due to Dyer and Frieze (Math Program 64:1-16, 1994).
Loading
Loading
No results