Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, August 31, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: József Balogh (The Ohio State Univ.)
We investigate the behavior of a randomized simplex algorithm on special linear programs. We use combinatorial models for Klee-Minty cubes, where we prove quadratic bounds for the expected running time on the random-edge simplex algorithm, improving a result of Gartner, Henk and Ziegler.
The model is the following: Consider a random 0,1 vector of length n. Choose uniformly randomly a 1 digit, and flip it and every digits to its right. The question is that what the expected time is to reach the all 0 vector. In particular we study the following (equivalent or dual) model: Starting from any configuration with finitely many 1's to the left of the origin, evolving by flipping each 1 to 0 exponentially at rate one, such that when a 1 flips, all bits to its right also flip. We show that the leftmost 1 moves right with linear speed.
(Joint work with Robin Pemantle )
Automatic MiSe System Software Version 1.4803M | admin login