Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem

DOI10.1007/S00454-004-2878-4zbMATH Open1073.90028arXivmath/0206125OpenAlexW2031822344MaRDI QIDQ705124FDOQ705124

Ulrich. Betke

Publication date: 25 January 2005

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We consider the homogenized linear feasibility problem, to find an $x$ on the unit sphere, satisfying $n$ line ar inequalities $a_i^{T}xge0$. 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.

Full work available at URL: https://arxiv.org/abs/math/0206125

Recommendations

• A polynomial projection algorithm for linear feasibility problems
• A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem
• A polynomial projection-type algorithm for linear programming
• Improved complexity results on solving real-number linear feasibility problems
• On Chubanov's Method for Linear Programming

zbMATH Keywords

combinatorial algorithmpolynomial algorithmLinear feasibility problemspherical feasibility problem

Mathematics Subject Classification ID

Convex programming (90C25) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational aspects related to convexity (52B55)

Cited In (17)

• Rescaled Coordinate Descent Methods for Linear Programming
• Rescaling Algorithms for Linear Conic Feasibility
• On Chubanov's Method for Linear Programming
• A comparative note on the relaxation algorithms for the linear semi-infinite feasibility problem
• Projection and Rescaling Algorithm for Finding Maximum Support Solutions to Polyhedral Conic Systems
• A simple method for convex optimization in the oracle model
• Greed Works: An Improved Analysis of Sampling Kaczmarz--Motzkin
• A deterministic rescaled perceptron algorithm
• Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• A polynomial projection-type algorithm for linear programming
• A simple method for convex optimization in the oracle model
• A strongly polynomial algorithm for approximate Forster transforms and its application to halfspace learning
• A Sampling Kaczmarz--Motzkin Algorithm for Linear Feasibility
• The colourful feasibility problem
• Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes
• Improved complexity results on solving real-number linear feasibility problems
• Geometric Rescaling Algorithms for Submodular Function Minimization

This page was built for publication: Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705124)