Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, March 29, 2011, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Yves Brise
Hypergraph matching is the problem of finding the maximum number of disjoint edges in a given hypergraph. This problem is NP-hard even for some restricted variants. It's even hard to approximate within certain factors. There are basically two approaches for approximation algorithms that have been studied in recent years. One is based on local search and the other one is based on linear and semidefinite programming relaxations. The former is more successful in terms of proven approximation ratio as well as algorithmic feasibility. In 2010, however, Yuk Hei Chan and Lap Chi Lau published a paper in which they bring the two worlds closer together, and give some profound insights on what the world of relaxations can and cannot do. This talk is going to be based on their paper "On Linear and Semidefinite Programming Relaxations for Hypergraph Matching".
Automatic MiSe System Software Version 1.4803M | admin login