# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Approximating Energy Efficient Paths in Wireless Multi-hop Networks

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Funke, S., Matijevic, D., & Sanders, P. (2003). Approximating Energy Efficient
Paths in Wireless Multi-hop Networks. In *Algorithms - ESA 2003: 11th Annual European Symposium*
(pp. 230-241). Berlin, Germany: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2C35-7

##### Abstract

Given the positions of $n$ sites in a radio network
we consider the problem of finding routes between any pair of sites
that minimize energy consumption and do not use more than some
constant number $k$ of hops. Known exact algorithms for this problem
required $\Omega(n \log n)$ per query pair $(p,q)$. In this paper we
relax the exactness requirement and only require approximate
$(1+\epsilon)$ solutions which allows us to derive schemes which
guarantee constant query time using linear space and
$O(n\log n)$ preprocessing time. The dependence on $\epsilon$ is
polynomial in $1/\epsilon$.
One tool used might be of independent interest:
For any pair of points $(p,q)\in P\subseteq\mathbb{Z}^2$
report in constant time the cluster pair $(A,B)$ representing $(p,q)$
in a well-separated pair decomposition of $P$.