| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142666 | Operations Research Letters | 2013 | 4 Pages |
Abstract
We present PTASs for the disk cover problem: given geometric objects and a finite set of disk centers, minimize the total cost for covering those objects with disks under a polynomial cost function on the disks’ radii. We describe the first FPTAS for covering a line segment when the disk centers form a discrete set, and a PTAS for when a set of geometric objects, described by polynomial algebraic inequalities, must be covered. The latter result holds for any dimension.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Pedro J. de Rezende, Flávio K. Miyazawa, Anderson T. Sasaki,