Relaxation, New Combinatorial and Polynomial Algorithms for the Linear Feasibility Problem

Ulrich Betke

We consider the homogenized linear feasibility problem, to find an $x$ on the unit sphere, satisfying $n$ line ar inequalities $a_i^{T}x\ge 0$. To solve this problem we consider the…