A strongly polynomial-time algorithm for the strict homogeneous linear-inequality feasibility problem

Paulo Oliveira ()

Mathematical Methods of Operations Research, 2014, vol. 80, issue 3, 267-284

Abstract: A strongly polynomial-time algorithm is proposed for the strict homogeneous linear-inequality feasibility problem in the positive orthant, that is, to obtain $$x\in \mathbb {R}^n$$ x ∈ R n , such that $$Ax > 0$$ A x > 0 , $$x> 0$$ x > 0 , for an $$m\times n$$ m × n matrix $$A$$ A , $$m\ge n$$ m ≥ n . This algorithm requires $$O(p)$$ O ( p ) iterations and $$O(m^2(n+p))$$ O ( m 2 ( n + p ) ) arithmetical operations to ensure that the distance between the solution and the iteration is $$10^{-p}$$ 10 - p . No matrix inversion is needed. An extension to the non-homogeneous linear feasibility problem is presented. Copyright Springer-Verlag Berlin Heidelberg 2014

Keywords: Strict linear-inequality feasibility; Linear programming; Strong polynomial method; Application of non-linear programming to feasibility problems; 15A39; 49M15 (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1007/s00186-014-0480-y (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:80:y:2014:i:3:p:267-284

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-014-0480-y

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().