Persistent Link:
http://hdl.handle.net/10150/291733
Title:
The modified covering problem on paths and trees
Author:
Lunday, Brian Joseph
Issue Date:
2001
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
The Modified Covering Problem (MCP) is introduced and theory is developed for solving it on paths and trees. First, the Modified Covering Problem is defined as a subset of the Conditional Covering Problem, and motivations are proposed for its study. Next, a literature review examines relevant, published material. The MCP is then formulated as a binary integer program, followed by an examination of the characteristics of its feasible solutions, optimality, and overall complexity. A polynomial algorithm is developed for the solving the MCP on paths with uniform link distances, and solving within 20% of optimality on paths with non-uniform link distances. Next, an exponential algorithm is developed to solve non-uniform link distance problems to optimality. The theory is then further expanded to construct an algorithm to develop strong upper and lower bounds for the optimal solution on trees with non-uniform link distances.
Type:
text; Thesis-Reproduction (electronic)
Keywords:
Mathematics.; Engineering, System Science.; Operations Research.
Degree Name:
M.S.
Degree Level:
masters
Degree Program:
Graduate College; Systems and Industrial Engineering
Degree Grantor:
University of Arizona
Advisor:
Goldberg, Jeffrey B.

Full metadata record

DC FieldValue Language
dc.language.isoen_USen_US
dc.titleThe modified covering problem on paths and treesen_US
dc.creatorLunday, Brian Josephen_US
dc.contributor.authorLunday, Brian Josephen_US
dc.date.issued2001en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractThe Modified Covering Problem (MCP) is introduced and theory is developed for solving it on paths and trees. First, the Modified Covering Problem is defined as a subset of the Conditional Covering Problem, and motivations are proposed for its study. Next, a literature review examines relevant, published material. The MCP is then formulated as a binary integer program, followed by an examination of the characteristics of its feasible solutions, optimality, and overall complexity. A polynomial algorithm is developed for the solving the MCP on paths with uniform link distances, and solving within 20% of optimality on paths with non-uniform link distances. Next, an exponential algorithm is developed to solve non-uniform link distance problems to optimality. The theory is then further expanded to construct an algorithm to develop strong upper and lower bounds for the optimal solution on trees with non-uniform link distances.en_US
dc.typetexten_US
dc.typeThesis-Reproduction (electronic)en_US
dc.subjectMathematics.en_US
dc.subjectEngineering, System Science.en_US
dc.subjectOperations Research.en_US
thesis.degree.nameM.S.en_US
thesis.degree.levelmastersen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.disciplineSystems and Industrial Engineeringen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorGoldberg, Jeffrey B.en_US
dc.identifier.proquest1405048en_US
dc.identifier.bibrecord.b41926237en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.