Name
Abstract | ||
|---|---|---|
This paper concerns geometric disk problems motivated by base station placement problems arising in wireless network design. We first study problems that involve maximizing the coverage under various interference-avoidance constraints. A representative problem for this type is the maximum weight independent set problem on unit disk graphs, for which we present an exact solution whose complexity is exponential but with a sublinear exponent. Specifically, our algorithm has time complexity 2O(驴mlogm), where m is the number of disks. We then study the problem of covering all the clients by a collection of disks of variable radii while minimizing the sum of radii, and present a PTAS for this problem. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/3-540-45471-3_10 | SWAT |
Keywords | Field | DocType |
base station placement problem,unit disk graph,exact solution,paper concerns geometric disk,base station placement problems,independent set problem,approximation schemes,sublinear exponent,exact algorithms,study problem,maximum weight,time complexity,representative problem,base station,independent set,wireless network | Sublinear function,Approximation algorithm,Base station,Mathematical optimization,Exact algorithm,Computer science,Algorithm,Independent set,Unit disk,Time complexity,Unit disk graph | Conference |
Volume | ISSN | ISBN |
2368 | 0302-9743 | 3-540-43866-1 |
Citations | PageRank | References |
10 | 0.76 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nissan Lev-Tov | 1 | 137 | 7.91 |
| David Peleg | 2 | 6662 | 824.19 |