Dynamic programming optimization in line of sight networks

DOI10.1016/J.IC.2019.104460MaRDI QIDQ2288208zbMATH OpenOpenAlexFDO

Authors Pavan Sangha, Prudence W. H. Wong, Michele Zito

Publication date 17 January 2020

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1806.01581

zbMATH Keywords

optimizationdynamic programmingapproximation algorithmsline-of-sight networks

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Approximation algorithms (68W25) Wireless sensor networks as related to computer science (68M18)

Abstract: Line of Sight (LoS) networks were designed to model wireless communication in settings which may contain obstacles restricting node visibility. For fixed positive integer $d$, and positive integer $omega$, a graph $G=(V,E)$ is a ($d$-dimensional) LoS network with range parameter $omega$ if it can be embedded in a cube of side size $n$ of the $d$-dimensional integer grid so that each pair of vertices in $V$ are adjacent if and only if their embedding coordinates differ only in one position and such difference is less than $omega$. In this paper we investigate a dynamic programming (DP) approach which can be used to obtain efficient algorithmic solutions for various combinatorial problems in LoS networks. In particular DP solves the Maximum Independent Set (MIS) problem in LoS networks optimally for any $omega$ on {em narrow} LoS networks (i.e. networks which can be embedded in a $nimeskimeskldotsimesk$ region, for some fixed $k$ independent of $n$). In the unrestricted case it has been shown that the MIS problem is NP-hard when $omega>2$ (the hardness 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 design of good approximation algorithms. In particular we present a 2-approximation algorithm and a fast polynomial time approximation scheme for the MIS problem in arbitrary $d$-dimensional LoS networks. Finally we comment on how the approach can be adapted to solve a number of important optimization problems in LoS networks.

Recommendations

• Independent Sets in Restricted Line of Sight Networks
• Independent sets in Line of Sight networks
• Finding large independent sets in line of sight networks
• Communication Problems in Random Line-of-Sight Ad-Hoc Radio Networks
• Approximation schemes for wireless networks

Cites work

• scientific article; zbMATH DE number 3786461 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Approximation algorithms for NP-hard problems.
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Communication Problems in Random Line-of-Sight Ad-Hoc Radio Networks
• Connectivity for line-of-sight networks in higher dimensions
• Gridline graphs: A review in two dimensions and an extension to higher dimensions
• Improved algorithm for maximum independent set on unit disk graph
• Independent Sets in Restricted Line of Sight Networks
• Independent sets in Line of Sight networks
• Induced embeddings into Hamming graphs
• Introduction to algorithms.
• Line-of-Sight Networks
• Line-of-sight percolation
• Matching theory
• On the efficiency of polynomial time approximation schemes
• Online algorithms: a survey
• Semi on-line algorithms for the partition problem
• Semi-online scheduling revisited
• Stochastic geometry and its applications

Cited in

(4)

• Independent Sets in Restricted Line of Sight Networks
• Finding large independent sets in line of sight networks
• Line-of-Sight Networks
• Independent sets in Line of Sight networks

This page was built for publication: Dynamic programming optimization in line of sight networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2288208)