Advanced Search

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

Cited in: Zbl 1216.65074 Zbl 1216.65073 Zbl 1172.65030 Zbl 1143.65045 Zbl 0983.65073 Zbl 0967.65078 Zbl 0944.65065 Zbl 0914.90221 Zbl 0954.65041 Zbl 0791.65042 Zbl 0810.65060 Zbl 0809.65056 Zbl 0748.90041 Zbl 0742.90054 Zbl 0741.90046 Zbl 0724.90039 Zbl 0715.90100 Zbl 0708.90053 Zbl 0708.90047 Zbl 0706.65059 Zbl 0697.90049 Zbl 0695.90056 Zbl 0688.90037 Zbl 0684.90062 Zbl 0681.65042 Zbl 0677.90044 Zbl 0675.90067 Zbl 0675.90050 Zbl 0667.65048 Zbl 0671.90043 Zbl 0641.90053 Zbl 0713.90049 Zbl 0662.65051 Zbl 0657.65081 Zbl 0641.90048 Zbl 0625.90088 Zbl 0625.90050 Zbl 0618.90058 Zbl 0607.65034 Zbl 0605.90089 Zbl 0625.90051 Zbl 0585.90056

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]