Master of Science (MS)
First Committee Member
Number of Pages
In this study of Monge properties I summarize a few aspects of the rich material based on these properties. Monge properties are related to the theory of convexity and just as convexity is important in classical Mathematics so is the theory of Monge properties important in Computer Science. In this thesis I will summarize a few aspects of Monge properties. I compare some of the different properties and show how that they all go back to Gaspard Monge's original ideas. I will highlight a number of new results in scheduling and show how Monge properties and Monge-like properties play a role. The thesis will also give results that come from implementing a linear time algorithm for scheduling which is based on Monge properties. I focus especially on batching problems, which are important for TCP/IP acknowledgement; The contribution of my thesis is a summary of important results regarding Monge as well a new implementation of a heuristic for an NP-hard scheduling problem. The main part of my program is a linear time subroutine which is based on a Monge-like property, called the "product property".
Applications; Matrices; Monge; Scheduling; Study
University of Nevada, Las Vegas
If you are the rightful copyright holder of this dissertation or thesis and wish to have the full text removed from Digital Scholarship@UNLV, please submit a request to firstname.lastname@example.org and include clear identification of the work, preferably with URL.
Pamballa, Revanth, "A study of Monge matrices with applications to scheduling" (2008). UNLV Retrospective Theses & Dissertations. 2421.