Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, September 21, 2023, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Anita Dürr
In the Exact Matching problem, one is given a graph with red and blue edges and an integer k. The goal is to determine whether the graph admits a perfect matching with exactly k red edges. A few years after its introduction in 1982 by Papadimitriou and Yannakakis, Mulmuley et al. showed a randomized algorithm solving Exact Matching, making it a member of the class RP. Determining whether Exact Matching is in P remains an open problem and very little progress has been made in that direction. In this talk I will focus on approximation algorithms that compute perfect matchings with almost k red edges and show the first one-sided approximation algorithm of that sort.
Automatic MiSe System Software Version 1.4803M | admin login