Campus Event Calendar
Event Entry
What and Who
The Arora-Kale algorithm for approximately solving SDP's using multiplicative weights updates
Khaled Elbassioni
Max-Planck-Institut für Informatik - D1
Lecture
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Wednesday, 14 December 2011
16:15
90 Minutes
E1 4
022
Saarbrücken
Abstract
In this (self-contained) lecture, I will explain the Arora-Kale's approach for approximately solving a class of SDP's using the matrix extension of the multiplicative weights updates method:
http://www.cs.princeton.edu/~arora/pubs/mmw.pdf
The main result is that for classes of SDP's, such as the ones arising in approximating MAXCUT, the multiplicative weights updates method can be used to give much faster algorithms than those obtained using interior-point methods.
Contact
Anonymous
--email hidden
passcode not visible
logged in users only
Anonymous, 12/12/2011 23:04
Anonymous, 12/12/2011 17:35
Anonymous, 12/12/2011 17:34 -- Created document.
Anonymous, 12/12/2011 17:35
Anonymous, 12/12/2011 17:34 -- Created document.