Relaxation, New Combinatorial and Polynomial Algorithms for the Linear Feasibility Problem
Relaxation, New Combinatorial and Polynomial Algorithms for the Linear
Feasibility Problem
复制标题
线性可行性问题的松弛、新组合和多项式算法
DOI：
10.1007/s00454-004-2878-4
复制
发表时间：
2002
影响因子：
0.8
通讯作者：
U. Betke
中科院分区：
文献类型：
--
作者：
U. Betke
抽象的
我们考虑了均质的线性可行性问题，以在
单位球体满足n线性不平等AITX \ ge 0。解决这个问题
问题我们考虑了球形简单的独立者的中心，
方面由约束的子集确定。结果，我们找到了一个新的
线性可行性问题的组合算法。如果我们允许
恢复，该算法变为多项式。我们指出算法
还解决了更通用的凸的可行性问题。而且，
数值实验表明该算法可能具有实际利益。
Abstract
We consider the homogenized linear feasibility problem, to find an x on the
unit sphere satisfying n linear inequalities aiTx \ge 0. To solve this
problem we consider the centers of the inspheres of spherical simplices, whose
facets are determined by a subset of the constraints. As a result we find a new
combinatorial algorithm for the linear feasibility problem. If we allow
rescaling, this algorithm becomes polynomial. We point out that the algorithm
also solves the more general convex feasibility problem. Moreover,
numerical experiments show that the algorithm could be of practical interest.