Award Date

1-1-2008

Degree Type

Thesis

Degree Name

Master of Science (MS)

Department

Computer Science

First Committee Member

Wolfgang Bein

Number of Pages

51

Abstract

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".

Keywords

Applications; Matrices; Monge; Scheduling; Study

Controlled Subject

Computer science

File Format

pdf

File Size

706.56 KB

Degree Grantor

University of Nevada, Las Vegas

Language

English

Permissions

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

Rights

IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/

Download


COinS