Files and links (1)
SubmittedOpen Access (License Unspecified), Open
Conference proceeding
Symmetric range assignment with disjoint MST constraints
Proceedings of the fifth international workshop on foundations of mobile computing
18 Aug 2008
Abstract
If V is a set of n points in the unit square [0,1] 2 , and if R:V-> Re + is an assignment of positive real numbers (radii) to to those points, define a graph G(R) as follows: [v,w] is an undirected edge if and only if the Euclidean distance d(v,w) is less than or equal to min(R(v),R(w)). Given α≥ 1 and k∈ Z + , let R k* be the range assignment that minimizes the function J(R) =sum limits v #8712; V R(v) α , subject to the constraint that G(R) has at least k edge-disjoint spanning trees. For n random points in [0,1] 2 , the expected value of the optimum, E(J(R k *)), is asymptotically Θ(n 1-α/2 ). This is proved by analyzing a crude approximation algorithm that finds a range assignment R k a such that the ratio J(R k a )/J(R k *) is bounded.
Metrics
6 Record Views
Details
- Title
- Symmetric range assignment with disjoint MST constraints
- Creators
- Eric Schmutz - Drexel University
- Publication Details
- Proceedings of the fifth international workshop on foundations of mobile computing
- Series
- DIALM-POMC '08
- Publisher
- Association for Computing Machinery (ACM)
- Resource Type
- Conference proceeding
- Language
- English
- Academic Unit
- Mathematics
- Scopus ID
- 2-s2.0-65249190738
- Other Identifier
- 991019173886904721