Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, September, 2020 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 167-170). / Linear inequality systems play a foundational role in Operations Research, but many fundamental structural and algorithmic questions about linear inequality systems remain unanswered. This thesis considers and addresses some of these questions. In the first chapter, we reconsider the ellipsoid algorithm applied to solving a system of linear inequalities. Unlike the simplex method and interior point methods, the ellipsoid algorithm has no mechanism for proving that a system is infeasible (in the real model of computation). Motivated by this, we develop an ellipsoid algorithm that produces a solution to a system or provides a simple proof that no solution exists. Depending on the dimensions and on other natural condition measures, the computational complexity of our algorithm may be worse than, the same as, or better than that of the standard ellipsoid algorithm.. In the second chapter, we reduce the problem of solving a homogeneous linear inequality system to the problem of finding the unique sink of a unique sink orientation (USO) in the vertex evaluation model of computation. We show the USOs of interest satisfy a local property that is not satisfied by all USOs that satisfy the Holt-Klee property. This addresses an open question that is motivated by the idea that such local structure could be leveraged algorithmically to develop faster algorithms or a strongly polynomial algorithm. In the third chapter, we make progress on a conjecture about a particular class of linear inequality systems that have balanced constraint matrices. A balanced matrix is a 0-1 matrix that does not contain a square submatrix of odd order with two ones per row and column. The conjecture asserts that every nonzero balanced matrix contains an entry equal to 1, which upon setting to 0, leaves the matrix balanced. / by Jourdain Bernard Lamperski. / Ph. D. / Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center
| Identifer | oai:union.ndltd.org:MIT/oai:dspace.mit.edu:1721.1/128971 |
| Date | January 2020 |
| Creators | Lamperski, Jourdain Bernard. |
| Contributors | Robert M. Freund., Massachusetts Institute of Technology. Operations Research Center., Massachusetts Institute of Technology. Operations Research Center, Sloan School of Management |
| Publisher | Massachusetts Institute of Technology |
| Source Sets | M.I.T. Theses and Dissertation |
| Language | English |
| Detected Language | English |
| Type | Thesis |
| Format | 170 pages, application/pdf |
| Rights | MIT theses may be protected by copyright. Please reuse MIT thesis content according to the MIT Libraries Permissions Policy, which is available through the URL provided., http://dspace.mit.edu/handle/1721.1/7582 |
Page generated in 0.0136 seconds