A tree-block decomposition-based heuristic for the minimum broadcast time. (26th November 2020)

• Record Type: Journal Article
• Authors: Sousa, Amaro De; Gallo, Gabriela; Gutiérrez, Santiago; Robledo, Franco; Rodrı́guez-Bocca, Pablo; Romero, Pablo
• Is Part Of: International journal of metaheuristics. Volume 7:Number 4(2019)
• Page Start: 379
• Page End: 401
• Publication Date: 2020-11-26
• Subjects: minimum broadcast time -- MBT -- computational complexity -- integer linear programming -- ILP -- heuristics; Heuristic algorithms -- Periodicals; 006.3105
• Languages: English
• ISSNs: 1755-2176

Abstract

The problem under study is the minimum broadcast time. Given an undirected connected graph and a singleton that owns a message, the goal is to broadcast this message as soon as possible, where the communication takes place between neighbouring-nodes in a selective fashion and each forwarding takes one time-slot. Historically, this problem finds applications in telephonic services; however, it serves as an inspirational problem for the design of current delay-tolerant forwarding schemes in modern communication systems like content delivery networks and peer-to-peer networks. The problem belongs to the NP -complete class. As a consequence, the literature offers heuristics, approximation algorithms and exact exponential-time solutions. The contributions of this paper are two-fold. First, an efficient integer linear programming formulation for the problem is provided. Second, a competitive heuristic called TreeBlock, is developed. A fair comparison between TreeBlock and previous heuristics highlights the effectiveness of our proposal.