
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.
near optimal solution, computational complexity, Linear programming, Analysis of algorithms and problem complexity, interior point method, polynomial time algorithm
near optimal solution, computational complexity, Linear programming, Analysis of algorithms and problem complexity, interior point method, polynomial time algorithm
| 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% |
