Name
Title | ||
|---|---|---|
Polynomial-time approximation schemes for piercing and covering with applications in wireless networks |
Abstract | ||
|---|---|---|
Let D be a set of disks of arbitrary radii in the plane, and let P be a set of points. We study the following three problems: (i) Assuming P contains the set of center points of disks in D, find a minimum-cardinality subset P^* of P (if exists), such that each disk in D is pierced by at least h points of P^*, where h is a given constant. We call this problem minimum h-piercing. (ii) Assuming P is such that for each D@?D there exists a point in P whose distance from D's center is at most @ar(D), where r(D) is D's radius and 0= |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.comgeo.2007.01.001 | Comput. Geom. |
Keywords | Field | DocType |
geometric optimization,minimum-cardinality subset,wireless network,approximation algorithms,discrete piercing,covering,polynomial-time approximation scheme,wireless networks,center point,h point,arbitrary radius,problem minimum h-piercing,polynomial time approximation scheme | Wireless network,Discrete mathematics,Approximation algorithm,Combinatorics,Existential quantification,Radius,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
39 | 3 | Computational Geometry: Theory and Applications |
Citations | PageRank | References |
7 | 0.49 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Paz Carmi | 1 | 321 | 43.14 |
| Matthew J. Katz | 2 | 225 | 19.92 |
| Nissan Lev-Tov | 3 | 137 | 7.91 |