Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, May 11, 2021, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
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 some approximation algorithms for the Exact Matching problem where we require the output to be a perfect matching and minimise the constraint violation.
Automatic MiSe System Software Version 1.4803M | admin login