@misc{KaibelPeinhardt2006, author = {Kaibel, Volker and Peinhardt, Matthias}, title = {On the Bottleneck Shortest Path Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9160}, number = {06-22}, year = {2006}, abstract = {The Bottleneck Shortest Path Problem is a basic problem in network optimization. The goal is to determine the limiting capacity of any path between two specified vertices of the network. This is equivalent to determining the unsplittable maximum flow between the two vertices. In this note we analyze the complexity of the problem, its relation to the Shortest Path Problem, and the impact of the underlying machine/computation model.}, language = {en} } @misc{GaertnerKaibel2005, author = {G{\"a}rtner, Bernd and Kaibel, Volker}, title = {Two New Bounds for the Random-Edge Simplex Algorithm}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8483}, number = {05-14}, year = {2005}, abstract = {We prove that the Random-Edge simplex algorithm requires an expected number of at most \$13n/sqrt(d)\$ pivot steps on any simple d-polytope with n vertices. This is the first nontrivial upper bound for general polytopes. We also describe a refined analysis that potentially yields much better bounds for specific classes of polytopes. As one application, we show that for combinatorial d-cubes, the trivial upper bound of \$2^d\$ on the performance of Random-Edge can asymptotically be improved by any desired polynomial factor in d.}, language = {en} }