THE ELLIPSOID ALGORITHM FOR LINEAR PROGRAMMING

Simple item page
dc.contributor.authorMARK, LAISIN
dc.date.accessioned2014-02-17T11:45:46Z
dc.date.available2014-02-17T11:45:46Z
dc.date.issued1998-08
dc.descriptionA 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, 1998en_US
dc.description.abstractThis 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.en_US
dc.identifier.urihttp://hdl.handle.net/123456789/1771
dc.language.isoenen_US
dc.subjectELLIPSOID,en_US
dc.subjectALGORITHM,en_US
dc.subjectLINEAR,en_US
dc.titleTHE ELLIPSOID ALGORITHM FOR LINEAR PROGRAMMINGen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
THE ELLIPSOID ALGORITHM FOR LINEAR PROGRAMMING.pdf
Size:
1.57 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.58 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
SCIENCE