Birkhoff-von Neumann定理在非二部图上的推广

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
证明了非二分图中的分数完美匹配可以在多项式时间内写成完美匹配的凸组合。这将Birkhoff-von Neumann定理从二分图推广到非二分图。Birkhoff和von Neumann的算法是贪婪的；它从给定的分数完美匹配开始，然后用适当的系数从它中依次“删除”完美匹配。这在非二分图中是失败的--任意移除完美匹配会导致一个非空但没有完美匹配的图。适当地使用奇数切可以节省时间。
---
英文标题：
《An Extension of the Birkhoff-von Neumann Theorem to Non-Bipartite Graphs》
---
作者：
Vijay V. Vazirani
---
最新提交年份：
2020
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Data Structures and Algorithms        数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类：Economics        经济学
二级分类：Theoretical Economics        理论经济学
分类描述：Includes theoretical contributions to Contract Theory, Decision Theory, Game Theory, General Equilibrium, Growth, Learning and Evolution, Macroeconomics, Market and Mechanism Design, and Social Choice.
包括对契约理论、决策理论、博弈论、一般均衡、增长、学习与进化、宏观经济学、市场与机制设计、社会选择的理论贡献。
--

---
英文摘要：
  We prove that a fractional perfect matching in a non-bipartite graph can be written, in polynomial time, as a convex combination of perfect matchings. This extends the Birkhoff-von Neumann Theorem from bipartite to non-bipartite graphs.   The algorithm of Birkhoff and von Neumann is greedy; it starts with the given fractional perfect matching and successively "removes" from it perfect matchings, with appropriate coefficients. This fails in non-bipartite graphs -- removing perfect matchings arbitrarily can lead to a graph that is non-empty but has no perfect matchings. Using odd cuts appropriately saves the day.
---
PDF链接：
https://arxiv.org/pdf/2010.05984

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：neumann neuman Mann bir Man 匹配 奇数 二分 bipartite 时间