Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem (Q705124): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Ulrich. Betke / rank | |||
Property / author | |||
Property / author: Ulrich. Betke / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2031822344 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: math/0206125 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 17:10, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem |
scientific article |
Statements
Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem (English)
0 references
25 January 2005
0 references
A new combinatorial algorithm is described in order to solve the homogenized linear feasibility problem of finding a point \(x\) on the unit sphere, satisfying \(n\) linear inequalities \(a^T_i x\geq0\). The use of the centers of the inspheres of spherical simplices, whose facets are determined by a subset of the constraints, leads to a combination of the algorithm of Agmon-Motzkin-Schoenberg with the algorithm of Khachiyan. A rescaling is periodically used to speed up the convergence, leading to the polynomiality of this algorithm. The geometry of the algorithm is thoroughly studied, resulting in an extension of the possibilities of application to more general convex feasibility problem. The investigation of practical ways to perform necessary calculations shows no particular difficulties and that the complexity of a single step is on average comparable with the simplex algorithm. Numerical examples are presented to emphasize the practical interest of this algorithm.
0 references
Linear feasibility problem
0 references
spherical feasibility problem
0 references
polynomial algorithm
0 references
combinatorial algorithm
0 references