THE ELLIPSOID ALGORITHM FOR LINEAR PROGRAMMING
THE ELLIPSOID ALGORITHM FOR LINEAR PROGRAMMING
No Thumbnail Available
Date
1998-08
Authors
MARK, LAISIN
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This thesis deals with the application of the ellipsoid
method to the solution of Linear Programming problems with
integer data in polynomial time. The thesis is divided into
four chapters.
In chapter one, we discuss the general Linear Programming
problem, the simplex method and duality in linear programming.
In chapter two, we discuss the ellipsoid algorithm for
the system of linear inequalities with rational or integer
data and show how it can be used to determine the feasibility
in polynomial time. In this chapter we also discuss some
antecedents of the ellipsoid algorithms and modifications of
the algorithm to achieve better rate of convergence.
Chapter three deals with the application of the ellipsoid
algorithm to solve a linear programming problems. Herein, we
have discussed Gacs and Lovasz approach, bisection method and
the method of sliding objective function. Finally, in this
chapter we discuss how exact solutions can be obtained from
approximate solutions.
Chapter four deals with the comparison of the ellipsoid
algorithm with the other linear programming algorithms. First
we have compared the ellipsoid algorithm discussed in chapter
two with the simplex algorithm discussed in chapter one.
Before going for its comparison with Karmarkar's algorithm, we
X
have briefly discussed Karmarkar's algorithm and then we have
critically examined its relation with the ellipsoid algorithm.
Finally we have presented concluding remarks.
Description
A THESIS SUBMITTED TO THE DEPARTMENT OF
MATHEMATICS, AHMADU BELLO UNIVERSITY, ZARIA IN
PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE
AWARD OF MASTER OF SCIENCE DEGREE IN MATHEMATICS.
AUGUST, 1998
Keywords
ELLIPSOID,, ALGORITHM,, LINEAR,