Dynamic Programming Optimization in Line of Sight Networks

Sangha, Pavan, Wong, Prudence ORCID: 0000-0001-7935-7245 and Zito, Michele (2020) Dynamic Programming Optimization in Line of Sight Networks. Information and Computation, 270. p. 104460.

Text swz-ic.pdf - Author Accepted Manuscript Available under License : See the attached licence file. Download (487kB) | Preview

Abstract

Line of Sight (LoS) networks were designed to model wireless communication in settings which may contain obstacles. For fixed positive integer d, and positive integer ω, a graph is a (d-dimensional) LoS network with range parameter ω if it can be embedded in a finite cube 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 ω. 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 ω, on narrow LoS networks (i.e. networks which can be embedded in a region, for some fixed k independent of n). In the unrestricted case it has been shown that the (decision version of the) problem is NP-hard when , for fixed . We describe how DP can be used as a building block in the design of good approximation algorithms in this case. In particular we present a semi-online polynomial-time approximation scheme for the MIS problem in narrow d-dimensional LoS networks, as well as a polynomial-time 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 prove similar results for a number of important optimization problems in LoS networks.

Item Type:	Article
Additional Information:	18 pages, 6 figures, submitted for journal publication
Uncontrolled Keywords:	networks, dynamic programming, optimization, approximation algorithms
Depositing User:	Symplectic Admin
Date Deposited:	19 Jan 2021 08:08
Last Modified:	18 Jan 2023 23:03
DOI:	10.1016/j.ic.2019.104460
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3114057

Available Versions of this Item

• Dynamic Programming Optimization in Line of Sight Networks. (deposited 19 Aug 2019 08:22)
  • Dynamic Programming Optimization in Line of Sight Networks. (deposited 19 Jan 2021 08:08) [Currently Displayed]