Optimization Online


The optimal design of low-latency virtual backbones

Hamidreza Validi (hamidreza.validi***at***okstate.edu)
Austin Buchanan (buchanan***at***okstate.edu)

Abstract: Two nodes of a wireless network may not be able to communicate with each other directly perhaps due to obstacles or insufficient signal strength. This necessitates the use of intermediate nodes to relay information. Often, one designates a (preferably small) subset of them to relay these messages (i.e., to serve as a virtual backbone for the wireless network) which can be seen as a connected dominating set (CDS) of the associated graph. Ideally, these communication paths should be short, leading to the notion of a latency-constrained CDS. In this paper, we point out several shortcomings of a previously studied formalization of a latency-constrained CDS and propose an alternative one. We introduce an integer programming formulation for the problem that has a variable for each node and imposes the latency constraints via an exponential number of cut-like inequalities. Two nice properties of this formulation are that: (1) it applies when distances are hop-based and also when they are weighted; and (2) it easily generalizes to ensure fault tolerance. We provide a branch-and-cut implementation of this formulation and compare it with a new polynomial-size formulation. Computational experiments demonstrate the superiority of the cut-like formulation. We also study related questions from computational complexity such as approximation hardness and answer an open problem regarding the fault diameter of graphs.

Keywords: connected dominating set; strongly connected dominating set; latency; delay; hop constraint; $k$-club; length-bounded cut; wireless networks; fault-tolerant; integer programming;

Category 1: Network Optimization

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Integer Programming

Citation: Accepted at INFORMS Journal on Computing

Download: [PDF]

Entry Submitted: 05/24/2018
Entry Accepted: 05/29/2018
Entry Last Modified: 06/03/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society