A PTAS for the disk cover problem of geometric objects

作     者：de Rezende, Pedro J. Miyazawa, Flavio K. Sasaki, Anderson T. 

作者机构：Univ Estadual Campinas Inst Comp Campinas SP Brazil 

出 版 物：《OPERATIONS RESEARCH LETTERS》 (运筹学快报)

年 卷 期：2013年第41卷第5期

页      面：552-555页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：CNPq Fapesp Faepex/Unicamp 

主　　题：Disk cover Approximation algorithm Computational geometry Wireless networks Sensor coverage 

摘      要：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. (C) 2013 Elsevier B.V. All rights reserved.