TY - GEN A1 - Kaibel, Volker A1 - Peinhardt, Matthias T1 - On the Bottleneck Shortest Path Problem N2 - 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. T3 - ZIB-Report - 06-22 KW - unsplittable flow KW - linear time algorithm KW - shortest path Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9160 ER - TY - GEN A1 - Gärtner, Bernd A1 - Kaibel, Volker T1 - Two New Bounds for the Random-Edge Simplex Algorithm N2 - 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. T3 - ZIB-Report - 05-14 Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8483 ER -