The cutting plane method is polynomial for perfect matchings
Event details
| Date | 28.10.2014 |
| Hour | 14:00 › 15:00 |
| Speaker |
László Végh, London School of Economics |
| Location |
INF 211
|
| Category | Conferences - Seminars |
Abstract: We exhibit a cutting plane algorithm that converges in polynomial time for the minimum-cost perfect matching problem. We start from the relaxation consisting of the degree constraints only, and add some of Edmonds's blossom inequalities 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.
Short bio:
László Végh is an assistant professor in the Operations Research 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 combinatorial optimisation related to connectivity, flows, and matchings, and their applications in game theory and network design.
Short bio:
László Végh is an assistant professor in the Operations Research 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 combinatorial optimisation related to connectivity, flows, and matchings, and their applications in game theory and network design.
Practical information
- Informed public
- Free
Organizer
- Nisheeth Vishnoi