Colourful Linear Programming and its Relatives
Colourful Linear Programming and its Relatives
复制标题
丰富多彩的线性规划及其相关
DOI：
--
复制
发表时间：
1997
影响因子：
1.7
通讯作者：
S. Onn
中科院分区：
文献类型：
--
作者：
I. Bárány;S. Onn
我们考虑以下线性编程的彩色概括：给定的点S1，...，SK⊂rd，称为颜色，一个点b∈Rd，决定是否有colourfult = {s1，...，...，...，...，... SK}使B∈Convt，如果有一个线性编程。 = 1d+1 convsi始终存在：我们描述了该问题的有效迭代近似算法，该算法找到了一个五颜六色的t，其凸面船体包含b的点e粘液，并分析其真实的算术和曲折时间复杂性，我们表明彩色线性编程是NP完整的，我们考虑了一类的线性代数亲属，并给出了对相关决策和计数问题的计算复杂性分类。 W1，W2-摩托 - 巴西 - 非源性问题的层次结构，并在组合几何形状中将彩色线性编程应用于Tverberg定理的算法问题。
We consider the following Colourful generalization of Linear Programming: given sets of points S1,..., Sk ⊂ Rd, referred to as colours, and a point b ∈ Rd, decide whether there is a colourfulT = {s1,..., sk} such that b ∈ convT, and if there is one, find it. Linear Programming is obtained by taking k = d + 1 and S1 =... = Sd+1. If k = d + 1 and b ∈ ∩i=1d+1 convSi then a solution always exists: we describe an efficient iterative approximation algorithm for this problem, that finds a colourful T whose convex hull contains a point e-close to b, and analyze its real arithmetic and Turing time complexities. In contrast, we show that Colourful Linear Programming is strongly NP-complete. We consider a class of linear algebraic relatives of Colourful Linear Programming, and give a computational complexity classification of the related decision and counting problems that arise. We also introduce and discuss the complexity of a hierarchy of w1, w2-Matroid-Basis-Nonbasis problems, and give an application of Colourful Linear Programming to the algorithmic problems of Tverberg's theorem in combinatorial geometry.