Approximation Algorithms for Rectangle Piercing Problems

Computer Science;piercing;stabbing;algorithm;approximation algorithm;approximation scheme;PTAS;shifting;rectangle;interval piercing

Mahmood, Abdullah-Al

University of Waterloo

关键词: Computer Science;    piercing;    stabbing;    algorithm;    approximation algorithm;    approximation scheme;    PTAS;    shifting;    rectangle;    interval piercing;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/1025/1/amahmood2005.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

Piercing problems arise often in facility location, which is a well-studied area of computational geometry. The general form of thepiercing problem discussed in this dissertation asks for the minimum number of facilities for a set of given rectangular demand regions such that each region has at least one facility located within it. It has been shown that even if all regions are uniform sized squares, theproblem is NP-hard. Therefore we concentrate on approximation algorithms for the problem. As the known approximation ratio for arbitrarily sized rectangles is poor, we restrict our effort todesigning approximation algorithms forunit-height rectangles. Oure-approximation scheme requiresn^O(1/ε²)time.We also consider the problem with restrictions like bounding the depth of a point and the width of the rectangles. The approximation schemes for these two cases take n^O(1/ε)time. We also show how to maintain a factor 2 approximation of the piercing set inO(log n) amortized time in an insertion-only scenario.