BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:The cutting plane method is polynomial for perfect matchings
DTSTART:20141028T140000
DTEND:20141028T150000
DTSTAMP:20260406T232430Z
UID:5151b7b9652eed6eb883829ff1f5f907d4ab10b33de6e33366b573f5
CATEGORIES:Conferences - Seminars
DESCRIPTION:László Végh\, London School of Economics\nAbstract: We exhi
 bit a cutting plane algorithm that converges in polynomial time for the mi
 nimum-cost perfect matching problem. We start from the relaxation consisti
 ng of the degree constraints only\, and add some of Edmonds's blossom ineq
 ualities as cutting planes. In every intermediate linear program we have a
  linear number of constraints and the optimal solution is half-integral. 
  This is a joint work with Karthik Chandrasekaran and Santosh Vempala.\nSh
 ort bio:\nLászló Végh is an assistant professor in the Operations Resea
 rch Group at the London School of Economics. He completed his PhD at the E
 ötvös University\, Budapest in 2010\, and was a postdoc at Georgia Tech 
 before joining the LSE. He is interested in fundamental questions in combi
 natorial optimisation related to connectivity\, flows\, and matchings\, an
 d their applications in game theory and network design.
LOCATION:INF 211
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR