BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Optimization and Incentives Seminar
SUMMARY:In Defense of Simplex’ Worst-Case Behavior - Yann
Disser (TU Berlin)
DTSTART;TZID=Europe/London:20140225T140000
DTEND;TZID=Europe/London:20140225T150000
UID:TALK50058AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/50058
DESCRIPTION:In the early 1970s\, by work of Klee and Minty (19
72) and Zadeh (1973)\, the Simplex Method\, the Ne
twork Simplex Method\, and the Successive Shortest
Path Algorithm have been proved guilty of exponen
tial worst-case behavior (for certain pivot rules)
. Since then\, the common perception is that these
algorithms can be fooled into investing senseless
effort by ‘bad instances’ such as\, e.g.\, Klee-M
inty cubes. This talk promotes a more favorable st
ance towards the algorithms’ worst-case behavior.
We argue that the exponential worst-case performan
ce is not necessarily a senseless waste of time\,
but may rather be due to the algorithms performing
meaningful operations and solving difficult probl
ems on their way. Given one of the above algorithm
s as a black box\, we show that using this black b
ox\, with polynomial overhead and a limited interf
ace\, we can solve any problem in NP. This also al
lows us to derive NP-hardness results for some rel
ated problems.
LOCATION:MR15\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge
CONTACT:Felix Fischer
END:VEVENT
END:VCALENDAR