.png){kind=icon}
返回
The red-blue-yellow matching problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.disopt.2026.100956.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们考虑红-蓝-黄匹配问题：给定两个自然数kR、kB和一个图G，其边被着色为红色、蓝色或黄色，目标是在这些约束条件下找到G的一个匹配，其中恰好包含kR条红色边和kB条蓝色边，并且具有最大基数。这是对著名的红-蓝匹配问题的一个自然推广，其复杂度状态未知：尽管存在随机多项式时间算法，但确定性算法在近四十年里一直难以实现。Yuster（2012）提出的解决红-蓝匹配问题的最佳已知确定性方法给出了一种加性近似。在本文中，我们为红-蓝-黄匹配问题展示了类似的结果，给出一个多项式时间确定性算法，该算法在自然假设下几乎精确地满足颜色要求，并且其基数与最优解相差不超过3。我们的算法结合了经典的线性规划技术与针对路径和循环等受限图类的特殊存在性结果。作为关键组成部分，我们证明了一种平面曲线的奇特拓扑性质，这是Grandoni和Zenklusen（2010）在预算匹配相关背景下提出的一个结果的加强版。
Keyword:
Red-blue matching
Matching polytope
Approximation algorithms
Plane curves
