Miscellaneous @Miscellaneous Verschiedenes

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author
 Author(s): Funke, Stefan Laue, Sören Naujoks, Rouven Lotker, Zvi dblp dblp dblp dblp Not MPG Author(s): Lotker, Zvi
 BibTeX citekey*: FunkeLaueLotkerNaujoks2006 Language: English

 Title, Howpublished
 Title*: Power Assignment Problems in Wireless Communication Howpublished: Internet

 Vol, No, pp., Year
 Month: Year: 2006 ISBN: Pages: 1-14

 Note: LaTeX Abstract: A fundamental class of problems in wireless communication is concerned with the assignment of suitable transmission powers to wireless devices/stations such that the resulting communication graph satisfies certain desired properties and the overall energy consumed is minimized. Many concrete communication tasks in a wireless network like broadcast, multicast, point-to-point routing, creation of a communication backbone, etc. can be regarded as such a power assignment problem. This paper considers several problems of that kind; for example one problem studied before in \cite{Carrots, Bilo} aims to select and assign powers to $k$ of the stations such that all other stations are within reach of at least one of the selected stations. We improve the running time for obtaining a $(1+\epsilon)$-approximate solution for this problem from $n^{((\alpha/\epsilon)^{O(d)})}$ as reported by Bilo et al. (\cite{Bilo}) to $O(n+ {(\frac{k^{2d+1}}{\epsilon^d})}^{\min{\{2k, (\alpha/\epsilon)^{O(d)} \}}})$ that is, we obtain a running time that is \emph{linear} in the network size. Further results include a constant approximation algorithm for the TSP problem under squared (non-metric!) edge costs, which can be employed to implement a novel data aggregation protocol, as well as efficient schemes to perform $k$-hop multicasts. Categories / Keywords: HyperLinks / References / URLs: Personal Comments: http://arxiv.org/abs/cs/0612121 File Upload: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: popular Appearance:

BibTeX Entry:
@MISC{FunkeLaueLotkerNaujoks2006,
AUTHOR = {Funke, Stefan and Laue, S{\"o}ren and Naujoks, Rouven and Lotker, Zvi},
TITLE = {Power Assignment Problems in Wireless Communication},
JOURNAL = {???},
HOWPUBLISHED = {Internet},
YEAR = {2006},
NUMBER = {?},
VOLUME = {?},
PAGES = {1--14},
}