论文标题
确切的匹配和TOP-K完美匹配问题
Exact Matching and the Top-k Perfect Matching Problem
论文作者
论文摘要
本说明的目的是将确切的匹配问题减少到顶部$ k $完美的匹配问题。与El Maalouly的早期工作一起，这表明这两个问题是多项式时间等效的。 确切的匹配问题是一个著名的40年历史的问题，但没有发现一个随机的，但没有发现确定性的多时间算法。顶级$ k $完美的匹配问题是找到完美匹配的问题，该匹配最大化了其中包含的$ k $最重的边缘的总重量。
The aim of this note is to provide a reduction of the Exact Matching problem to the Top-$k$ Perfect Matching Problem. Together with earlier work by El Maalouly, this shows that the two problems are polynomial-time equivalent. The Exact Matching Problem is a well-known 40 years old problem for which a randomized, but no deterministic poly-time algorithm has been discovered. The Top-$k$ Perfect Matching Problem is the problem of finding a perfect matching which maximizes the total weight of the $k$ heaviest edges contained in it.
