Award Date


Degree Type


Degree Name

Master of Science (MS)


Computer Science

First Committee Member

Wolfgang Bein

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

Controlled Subject

Computer science

File Format


File Size

706.56 KB

Degree Grantor

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 and include clear identification of the work, preferably with URL.


IN COPYRIGHT. For more information about this rights statement, please visit