A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem (Q486939): Difference between revisions

The author proposes a strongly polynomial-time algorithm for the strict homogeneous linear- inequality feasibility problem in the positive orthant, that is, to obtain \(x \in \mathbb R^n\), such that \(A x > 0\), \(x >0\), for an \(m \times n\) matrix \(A\), \(m \leq n\). An extension to the non-homogeneous linear feasibility problem is presented.

0 references

reviewed by

Hans Benker

0 references

zbMATH Keywords

strict linear-inequality feasibility

0 references

linear programming

0 references

strong polynomial method

0 references

application of nonlinear programming to feasibility problems

0 references

describes a project that uses

ART3+

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/s00186-014-0480-y

0 references

cites work

The Relaxation Method for Linear Inequalities

0 references

A primal-dual interior point method whose running time depends only on the constraint matrix

0 references

On Chubanov's Method for Linear Programming

0 references

On Projection Algorithms for Solving Convex Feasibility Problems

0 references

On the use of Cimmino's simultaneous projections method for computing a solution of the inverse problem in radiation therapy treatment planning

0 references

On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints

0 references

New methods for linear inequalities

0 references

Q5769827

0 references

A strongly polynomial algorithm for linear systems having a binary solution

0 references

On the complexity of solving feasible systems of linear inequalities specified with approximate data

0 references

On the non-polynomiality of the relaxation method for systems of linear inequalities

0 references

Complexity Analysis of an Interior Cutting Plane Method for Convex Feasibility Problems

0 references

The method of projections for finding the common point of convex sets

0 references

Fundamentals of Computerized Tomography

0 references

A fast algorithm for solving a linear feasibility problem with application to intensity-modulated radiation therapy

0 references

Relaxation methods for image reconstruction

0 references

An Algorithm for Linear Inequalities and its Applications

0 references

La méthode des centres dans un espace topologique

0 references

Q5535546

0 references

Q4197641

0 references

On the complexity of approximating the maximal inscribed ellipsoid for a polytope

0 references

Solvability and Consistency for Linear Equations and Inequalities

0 references

On a relaxation method of solving systems of linear inequalities

0 references

The Relaxation Method for Linear Inequalities

0 references

Q3967358

0 references

Location of the Maximum on Unimodal Surfaces

0 references

Q3028166

0 references

Q5187067

0 references

Q4204004

0 references

A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs

0 references

A new algorithm for minimizing convex functions over convex sets

0 references

How partial knowledge helps to solve linear programs

0 references

Identifiers

zbMATH Open document ID

1308.65095

0 references

DOI

10.1007/s00186-014-0480-y

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:486939

@@ Property / review text @@
+The author proposes a strongly polynomial-time algorithm for the strict homogeneous linear- inequality feasibility problem in the positive orthant, that is, to obtain \(x \in \mathbb R^n\), such that \(A x > 0\), \(x >0\), for an \(m \times n\) matrix \(A\), \(m \leq n\). An extension to the non-homogeneous linear feasibility problem is presented.
+Normal rank
@@ Property / reviewed by @@
+Hans Benker
@@ Property / reviewed by: Hans Benker / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+K05
@@ Property / Mathematics Subject Classification ID: 65K05 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+A39
@@ Property / Mathematics Subject Classification ID: 15A39 / rank @@
+Normal rank
@@ Property / Mathematics Subject Classification ID @@
+C05
@@ Property / Mathematics Subject Classification ID: 90C05 / rank @@
+Normal rank
@@ Property / zbMATH DE Number @@
+6387655
@@ Property / zbMATH DE Number: 6387655 / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+strict linear-inequality feasibility
@@ Property / zbMATH Keywords: strict linear-inequality feasibility / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+linear programming
@@ Property / zbMATH Keywords: linear programming / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+strong polynomial method
@@ Property / zbMATH Keywords: strong polynomial method / rank @@
+Normal rank
@@ Property / zbMATH Keywords @@
+application of nonlinear programming to feasibility problems
+Normal rank
@@ Property / describes a project that uses @@
+ART3+
@@ Property / describes a project that uses: ART3+ / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00186-014-0480-y
+Normal rank
@@ Property / OpenAlex ID @@
+W2014479920
@@ Property / OpenAlex ID: W2014479920 / rank @@
+Normal rank
@@ Property / cites work @@
+The Relaxation Method for Linear Inequalities
@@ Property / cites work: The Relaxation Method for Linear Inequalities / rank @@
+Normal rank
@@ Property / cites work @@
+A primal-dual interior point method whose running time depends only on the constraint matrix
+Normal rank
@@ Property / cites work @@
+On Chubanov's Method for Linear Programming
@@ Property / cites work: On Chubanov's Method for Linear Programming / rank @@
+Normal rank
@@ Property / cites work @@
+On Projection Algorithms for Solving Convex Feasibility Problems
+Normal rank
@@ Property / cites work @@
+On the use of Cimmino's simultaneous projections method for computing a solution of the inverse problem in radiation therapy treatment planning
+Normal rank
@@ Property / cites work @@
+On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints
+Normal rank
@@ Property / cites work @@
+New methods for linear inequalities
@@ Property / cites work: New methods for linear inequalities / rank @@
+Normal rank
@@ Property / cites work @@
+Q5769827
@@ Property / cites work: Q5769827 / rank @@
+Normal rank
@@ Property / cites work @@
+A strongly polynomial algorithm for linear systems having a binary solution
+Normal rank
@@ Property / cites work @@
+On the complexity of solving feasible systems of linear inequalities specified with approximate data
+Normal rank
@@ Property / cites work @@
+On the non-polynomiality of the relaxation method for systems of linear inequalities
+Normal rank
@@ Property / cites work @@
+Complexity Analysis of an Interior Cutting Plane Method for Convex Feasibility Problems
+Normal rank
@@ Property / cites work @@
+The method of projections for finding the common point of convex sets
+Normal rank
@@ Property / cites work @@
+Fundamentals of Computerized Tomography
@@ Property / cites work: Fundamentals of Computerized Tomography / rank @@
+Normal rank
@@ Property / cites work @@
+A fast algorithm for solving a linear feasibility problem with application to intensity-modulated radiation therapy
+Normal rank
@@ Property / cites work @@
+Relaxation methods for image reconstruction
@@ Property / cites work: Relaxation methods for image reconstruction / rank @@
+Normal rank
@@ Property / cites work @@
+An Algorithm for Linear Inequalities and its Applications
+Normal rank
@@ Property / cites work @@
+La méthode des centres dans un espace topologique
+Normal rank
@@ Property / cites work @@
+Q5535546
@@ Property / cites work: Q5535546 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4197641
@@ Property / cites work: Q4197641 / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of approximating the maximal inscribed ellipsoid for a polytope
+Normal rank
@@ Property / cites work @@
+Solvability and Consistency for Linear Equations and Inequalities
+Normal rank
@@ Property / cites work @@
+On a relaxation method of solving systems of linear inequalities
+Normal rank
@@ Property / cites work @@
+The Relaxation Method for Linear Inequalities
@@ Property / cites work: The Relaxation Method for Linear Inequalities / rank @@
+Normal rank
@@ Property / cites work @@
+Q3967358
@@ Property / cites work: Q3967358 / rank @@
+Normal rank
@@ Property / cites work @@
+Location of the Maximum on Unimodal Surfaces
@@ Property / cites work: Location of the Maximum on Unimodal Surfaces / rank @@
+Normal rank
@@ Property / cites work @@
+Q3028166
@@ Property / cites work: Q3028166 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5187067
@@ Property / cites work: Q5187067 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4204004
@@ Property / cites work: Q4204004 / rank @@
+Normal rank
@@ Property / cites work @@
+A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
+Normal rank
@@ Property / cites work @@
+A new algorithm for minimizing convex functions over convex sets
+Normal rank
@@ Property / cites work @@
+How partial knowledge helps to solve linear programs
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:486939