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

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

2002-06-12

arxiv.org/abs/math/0206125v1

Mathematics

Optimization and Control

Scientific paper

We consider the homogenized linear feasibility problem, to find an $x$ on the unit sphere, satisfying $n$ line ar inequalities $a_i^Tx\ge 0$. To solve this problem we consider the centers of the insphere of spherical simpl ices, whose facets are determined by a subset of the constraints. As a result we find a new combinatorial algor ithm for the linear feasibility problem. If we allow rescaling this algorithm becomes polynomial. We point out that the algorithm solves as well the more general convex feasibility problem. Moreover numerical experiments s how that the algorithm could be of practical interest.

Affiliated with

Also associated with

No associations

Rating

Relaxation, New Combinatorial and Polynomial Algorithms for the Linear Feasibility Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Relaxation, New Combinatorial and Polynomial Algorithms for the Linear Feasibility Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Relaxation, New Combinatorial and Polynomial Algorithms for the Linear Feasibility Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-496782