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.
| Identifer | oai:union.ndltd.org:arizona.edu/oai:arizona.openrepository.com:10150/291733 |
| Date | January 2001 |
| Creators | Lunday, Brian Joseph |
| Contributors | Goldberg, Jeffrey B. |
| Publisher | The University of Arizona. |
| Source Sets | University of Arizona |
| Language | en_US |
| Detected Language | English |
| Type | text, Thesis-Reproduction (electronic) |
| 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. |
Page generated in 0.0015 seconds