Investigations on two classes of covering problems

Simple item page
dc.contributor.authorThom, Mark
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorBenkoczi, Robert
dc.date.accessioned2017-02-03T16:21:54Z
dc.date.available2017-02-03T16:21:54Z
dc.date.issued2017
dc.degree.levelPh.Den_US
dc.description.abstractCovering problems fall within the broader category of facility location, a branch of combinatorial optimization concerned with the optimal placement of service facilities in some geometric space. This thesis considers two classes of covering problems. The first, Covering with Variable Capacities (CVC), was introduced in [1] and adds a notion of capacity to the classical Uncapacitated Facility Location problem. That is, each facility has a fixed maximum quantity of clients it can serve. The objective of each variant of CVC is either to serve all clients, the greatest number of clients possible, or all clients using the least number of facilities possible. We provide approximation algorithms, and in a few select cases, optimal algorithms, for all three variants of CVC. The second class of covering problems is barrier coverage. When the purpose of coverage is surveillance rather than service, a cost effective approach to the problem of intruder detection is to place sensors along the boundary, or barrier, of the surveilled region. A barrier coverage is complete when any intrusion is sure to be detected by some sensor. We limit our consideration of barrier coverage to the one-dimensional case, where the region is a line segment. Sensors are themselves line segments, whose span forms a detection range. The objective of barrier coverage as considered here is to form a complete barrier coverage while minimizing the total movement cost, the sum of the weighted distances moved by each sensor in the solution. We show that, by assuming the sensors lie in initial positions where their detection ranges are disjoint from the barrier, one-dimensional barrier coverage can be solved with an FPTAS. Along the way to developing the FPTAS, we give a fast, simple 2-approximation algorithm for weighted disjoint barrier coverage.en_US
dc.embargoNoen_US
dc.identifier.urihttps://hdl.handle.net/10133/4774
dc.language.isoen_USen_US
dc.proquest.subject0364en_US
dc.proquest.subject0984en_US
dc.proquestyesYesen_US
dc.publisherLethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Scienceen_US
dc.publisher.departmentDepartment of Mathematics and Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectapproximation algorithmsen_US
dc.subjectcovering problemsen_US
dc.subjectfacility locationen_US
dc.titleInvestigations on two classes of covering problemsen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
THOM_MARK_PHD_2017.pdf
Size:
866.18 KB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
3.19 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses