English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Line of Sight (LoS) networks were designed to model wireless communication insettings which may contain obstacles restricting node visibility. For fixedpositive integer $d$, and positive integer $\omega$, a graph $G=(V,E)$ is a($d$-dimensional) LoS network with range parameter $\omega$ if it can beembedded in a cube of side size $n$ of the $d$-dimensional integer grid so thateach pair of vertices in $V$ are adjacent if and only if their embeddingcoordinates differ only in one position and such difference is less than$\omega$.  In this paper we investigate a dynamic programming (DP) approach which can beused to obtain efficient algorithmic solutions for various combinatorialproblems in LoS networks. In particular DP solves the Maximum Independent Set(MIS) problem in LoS networks optimally for any $\omega$ on {\em narrow} LoSnetworks (i.e. networks which can be embedded in a $n \times k \times k \ldots\times k$ region, for some fixed $k$ independent of $n$). In the unrestrictedcase it has been shown that the MIS problem is NP-hard when $ \omega > 2$ (thehardness proof goes through for any $\omega=O(n^{1-\delta})$, for fixed$0<\delta<1$). We describe how DP can be used as a building block in the designof good approximation algorithms. In particular we present a 2-approximationalgorithm and a fast polynomial time approximation scheme for the MIS problemin arbitrary $d$-dimensional LoS networks. Finally we comment on how theapproach can be adapted to solve a number of important optimization problems inLoS networks.

Dynamic Programming Optimization in Line of Sight Networks