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

Simple item page
dc.creatorBetke, Ulrich
dc.date2002-06-12
dc.date.accessioned2026-07-07T04:49:05Z
dc.date.available2026-07-07T04:49:05Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/math/0206125
dc.identifierhttp://arxiv.org/abs/math/0206125
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/64290
dc.subjectOptimization and Control
dc.subject90C05; 90C25; 52B55
dc.titleRelaxation, New Combinatorial and Polynomial Algorithms for the Linear Feasibility Problem
dc.typetext

Files

Collections

arXiv