Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao COMBINATORICAarrow_drop_down
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
COMBINATORICA
Article . 1984 . Peer-reviewed
License: Springer TDM
Data sources: Crossref
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 1984
Data sources: zbMATH Open
DBLP
Conference object
Data sources: DBLP
DBLP
Article . 1984
Data sources: DBLP
versions View all 5 versions
addClaim

A new polynomial-time algorithm for linear programming

Authors: Narendra Karmarkar;

A new polynomial-time algorithm for linear programming

Abstract

This paper discusses a new polynomial time algorithm for linear programming (LP). It is an interior point method whose worst case computational complexity is \(0(n^{3.5}L)\) arithmetic operations on 0(L) bit numbers, where n is the number of variables and L is the number of bits in the input. The complexity bound for this algorithm is better than that for the ellipsoid algorithm by a factor of \(0(n^{2.5}).\) The author shows that every LP can be transformed into the form: min cx subject to \(x\in \Omega \cap \Delta\), where \(\Omega\) is the subspace \(\{\) \(x: Ax=0\}\) and \(\Delta\) is the simplex \(\{\) \(x: x\geq 0\) and \(\Sigma x_ j=1\}\), and the minimum objective value in the problem is known to be zero. His algorithm solves the LP in this form. Let \(a_ 0=(1/n)e\), where e is the vector of all 1's in \(R^ n\). Let \(B(a_ 0,r)\), \(B(a_ 0,R)\) be respectively the largest sphere with center \(a_ 0\) lying in \(\Delta\), and the smallest sphere with center \(a_ 0\) containing \(\Delta\). Then \(R/r=(n-1)\). Using this he shows that if \(a_ 0\) is feasible, \(a_ 0-r\hat c\), where \(\hat c\) is the normalized vector which in the orthogonal projection of c in \(\Omega\), is chosen to the minimum objective value by a factor of (1-1/(n-1)). This is the main result on which the algorithm is based. The algorithm is initiated with a feasible solution \(x^ 0>0\), and it generates a descent sequence of positive feasible points \(x^ 0,x^ 1,..\).. In the kth step, the point \(x^ k\) is brought into the center of the simplex by a projective transformation, a step of the form described above is taken, and the inverse projective transformation is applied, leading to the next point \(x^{k+1}\), reducing the objective function value by a factor of 0(n). The sequence of points generated, converges to a near optimal solution in polynomial time.

Related Organizations
Keywords

near optimal solution, computational complexity, Linear programming, Analysis of algorithms and problem complexity, interior point method, polynomial time algorithm

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    3K
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Top 0.01%
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Top 0.01%
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Top 1%
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
3K
Top 0.01%
Top 0.01%
Top 1%
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!