Investigations on two classes of covering problems

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

Authors

• Thom, Mark
• University of Lethbridge. Faculty of Arts and Science

• approximation algorithms
• covering problems
• facility location

Identifier

hdl:10133/4774

OAI identifier oai:identifier

oai:opus.uleth.ca:10133/4774