Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, October 25, 2022, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Nicolas El Maalouly
In the Exact Matching problem, we are given a graph with edges colored red and blue, and an integer k. The goal is to output a perfect matching with exactly k red edges. After introducing the problem in 1982, Papadimitriou and Yannakakis conjectured it to be NP-hard. Soon after, however, Mulmuley et al. (1987) proved that it can be solved in randomized polynomial time, which makes it unlikely to be NP-hard. Determining whether Exact Matching is in P remains an open problem and very little progress has been made towards that goal. Yuster (2012) showed that relaxing the perfect matching constraint by even one edge results in a simple deterministic polynomial-time algorithm. Generalisations of the problem have been well studied in the literature. Such generalisations include Bounded Color Matchings, where we have multiple color constraints, and Budgeted Matchings, where the color constraints (i.e. cardinality constraints) are replaced by budget constrains. Approximation algorithms have been studied for these problems, but none of the prior results work when enforcing a perfect matching constraint. In this talk I show how we can transform the Exact Matching problem into an optimization problem while keeping the perfect matching requirement and then present approximation algorithms for it.
Automatic MiSe System Software Version 1.4803M | admin login