The Rainbow at the End of the Line - A PPAD Formulation of the Colorful Carathéodory Theorem with Applications
The Rainbow at the End of the Line - A PPAD Formulation of the Colorful Carathéodory Theorem with Applications
复制标题
线尾的彩虹 - 彩色卡拉西奥多里定理的 PPAD 公式及其应用
DOI：
10.1137/1.9781611974782.87
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Yannik
中科院分区：
文献类型：
--
作者：
Meunier;Frédéric;Mulzer;Wolfgang;Sarrabezolles;Pauline;Yannik
设C1，.，Cd +i bed+ 1个点集，每个点集在其凸船体中包含原点.一个子集Cof被称为C1，.，Cd+1的彩色选择（或彩虹），如果它恰好包含每个集合Ci中的一个点。彩色Carathéodory定理指出，总是存在C1，.，Cd+1的彩色选择，其原点在其凸船体中。这个定理非常一般，可以用来证明高维离散几何中的其他几个存在性定理，如中心点定理或Tverberg定理。彩色Carathéodory问题（ColorfulCarathéodory）是找到这样一个彩色选择的计算问题。尽管在过去的几个努力，计算复杂性ColorfulCarathéodoryin任意维仍然是开放的。我们表明，ColorfulCarathéodorylies的复杂性类PPAD和PLS的交集。这使得它成为PPAD和PLS中为数不多的几何问题之一，这些问题在多项式时间内不可解。此外，它意味着计算中心点，计算Tverberg分区，计算点与大单纯形深度的问题包含在PPAD PLS。这是第一个非平凡的上限上的复杂性，这些problems.Finally，我们表明，我们的PPAD制定导致一个多项式时间算法的特殊情况下ColorfulCarathéodorin，我们只有两个颜色classesC1andC2inddimensions，每个原点在其凸船体，我们想找到一个集的一半点，从每个颜色类，包含在其凸船体的起源。
LetC1,…,Cd+i bed+ 1 point sets in ℝd, each containing the origin in its convex hull. A subsetCof is called a colorful choice (or rainbow) forC1,…, Cd+1, if it contains exactly one point from each setCi.The colorful Carathéodory theorem states that there always exists a colorful choice forC1,…, Cd+1that has the origin in its convex hull. This theorem is very general and can be used to prove several other existence theorems in high-dimensional discrete geometry, such as the centerpoint theorem or Tverberg's theorem. The colorful Carathéodory problem (ColorfulCarathéodory) is the computational problem of finding such a colorful choice. Despite several efforts in the past, the computational complexity of ColorfulCarathéodoryin arbitrary dimension is still open.We show that ColorfulCarathéodorylies in the intersection of the complexity classes PPAD and PLS. This makes it one of the few geometric problems in PPAD and PLS that are not known to be solvable in polynomial time. Moreover, it implies that the problem of computing centerpoints, computing Tverberg partitions, and computing points with large simplicial depth is contained in PPAD Π PLS. This is the first nontrivial upper bound on the complexity of these problems.Finally, we show that our PPAD formulation leads to a polynomial-time algorithm for a special case of ColorfulCarathéodoryin which we have only two color classesC1andC2inddimensions, each with the origin in its convex hull, and we would like to find a set with half the points from each color class that contains the origin in its convex hull.
登录
查看更多内容
丰富多彩的线性规划及其相关
影响因子：
1.7
作者：
I. Bárány;S. Onn
通讯作者：
S. Onn
通过数域的特维尔伯格定理
DOI：
--
发表时间：
1992
期刊：
影响因子：
--
作者：
K. S. Sarkaria
通讯作者：
K. S. Sarkaria
持续本地搜索
DOI：
--
发表时间：
2011
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
C. Daskalakis;C. Papadimitriou
通讯作者：
C. Papadimitriou
线性规划 O(n3L) 算法中的长步
影响因子：
2.7
作者：
K. Anstreicher;R. Bosch
通讯作者：
R. Bosch
一般测度定理
DOI：
10.1112/jlms/s1-21.4.291
发表时间：
1946
影响因子：
1.2
作者：
R. Rado
通讯作者：
R. Rado