Investigations on two classes of covering problems
Date
2017
Authors
Thom, Mark
University of Lethbridge. Faculty of Arts and Science
Journal Title
Journal ISSN
Volume Title
Publisher
Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science
Abstract
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.
Description
Keywords
approximation algorithms , covering problems , facility location