Miscellaneous
@Miscellaneous
Verschiedenes


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:









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

Abstract, Links, ©

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},
}


Entry last modified by Rouven Naujoks, 02/16/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christine Kiesel
Created
03/16/2007 09:35:38 PM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Rouven Naujoks
Uwe Brahm
Uwe Brahm
Christine Kiesel
Christine Kiesel
Edit Dates
02/16/2009 11:00:16 AM
2007-06-28 15:07:44
2007-06-28 15:07:17
02.05.2007 17:13:33
03.04.2007 11:58:41
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section
http://arxiv.org/PS_cache/cs/pdf/0612/0612121.pdf