BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:In Defense of Simplex’ Worst-Case Behavior - Yann Disser (TU Ber
 lin)
DTSTART:20140225T140000Z
DTEND:20140225T150000Z
UID:TALK50058@talks.cam.ac.uk
CONTACT:Felix Fischer
DESCRIPTION:In the early 1970s\, by work of Klee and Minty (1972) and Zade
 h (1973)\, the Simplex Method\, the Network Simplex Method\, and the Succe
 ssive Shortest Path Algorithm have been proved guilty of exponential worst
 -case behavior (for certain pivot rules). Since then\, the common percepti
 on is that these algorithms can be fooled into investing senseless effort 
 by ‘bad instances’ such as\, e.g.\, Klee-Minty cubes. This talk promot
 es a more favorable stance towards the algorithms’ worst-case behavior. 
 We argue that the exponential worst-case performance is not necessarily a 
 senseless waste of time\, but may rather be due to the algorithms performi
 ng meaningful operations and solving difficult problems on their way. Give
 n one of the above algorithms as a black box\, we show that using this bla
 ck box\, with polynomial overhead and a limited interface\, we can solve a
 ny problem in NP. This also allows us to derive NP-hardness results for so
 me related problems.
LOCATION:MR15\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR