Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

Query:
Fill in the form and click »Search«...
Format:
Display: entries per page entries
Zbl 0557.90065
Karmarkar, N.
A new polynomial-time algorithm for linear programming.
(English)
[J] Combinatorica 4, 373-395 (1984). ISSN 0209-9683

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\sp{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\sp{2.5}).$ \par 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\ge 0$ and $\Sigma x\sb j=1\}$, and the minimum objective value in the problem is known to be zero. His algorithm solves the LP in this form. \par Let $a\sb 0=(1/n)e$, where e is the vector of all 1's in $R\sp n$. Let $B(a\sb 0,r)$, $B(a\sb 0,R)$ be respectively the largest sphere with center $a\sb 0$ lying in $\Delta$, and the smallest sphere with center $a\sb 0$ containing $\Delta$. Then $R/r=(n-1)$. Using this he shows that if $a\sb 0$ is feasible, $a\sb 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. \par The algorithm is initiated with a feasible solution $x\sp 0>0$, and it generates a descent sequence of positive feasible points $x\sp 0,x\sp 1,..$.. In the kth step, the point $x\sp 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\sp{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.
[K.G.Murty]
MSC 2000:
*90C05 Linear programming
68Q25 Analysis of algorithms and problem complexity

Keywords: polynomial time algorithm; interior point method; computational complexity; near optimal solution

Highlights
Master Server