论文标题
部分可观测时空混沌系统的无模型预测
The Exact Bipartite Matching Polytope Has Exponential Extension Complexity
论文作者
论文摘要
给定带有彩色红色或蓝色和整数$ k $的图表，确切的完美匹配问题询问是否存在与恰好$ k $红色边缘的完美匹配。存在一种随机的聚类时平行算法来解决此问题，可以追溯到八十年代，但即使是双分部分图，也不知道确定性的多项式时间算法。在本文中，我们表明，没有次指定大小的线性程序可以描述双方图中精确匹配的凸壳。实际上，我们证明了更强大的东西，没有一个次数大小的线性程序来描述具有奇数红色边缘的完美匹配的凸面。
Given a graph with edges colored red or blue and an integer $k$, the exact perfect matching problem asks if there exists a perfect matching with exactly $k$ red edges. There exists a randomized polylogarithmic-time parallel algorithm to solve this problem, dating back to the eighties, but no deterministic polynomial-time algorithm is known, even for bipartite graphs. In this paper we show that there is no sub-exponential sized linear program that can describe the convex hull of exact matchings in bipartite graphs. In fact, we prove something stronger, that there is no sub-exponential sized linear program to describe the convex hull of perfect matchings with an odd number of red edges.
