DESIGNING PROVABLY GOOD HEURISTICS FOR RAPID INFORMATION DISSEMINATION PROBLEMS
Abstract
A fundamental role of complex networks is to propagate information so that agents in one part of the network are kept informed of the status of nodes in other parts with a low latency. Information dissemination problems in networks capture this key requirement by specifying the underlying model of information transmission, and the demand requirements for transmission such as the set of important nodes from which information freshness is vital. The main goal of this project is to develop a comprehensive theory of provably near-optimal approximation algorithms for network information dissemination problems encompassing both different models of transmission and a variety of dissemination demand requirements. Additionally, a new generalization of these problems is proposed using a vector clock model arising from distributed systems and social networking, and relate them to the more classical models. The proposed research will investigate the computational relationships and reductions between the various models and develop new ideas for designing approximation algorithms both for the newly proposed models and for improving upon the current best performance guarantees. A key outcome of this work will be the design of better centralized schedules for information flow in arbitrary networks, with the ability to specify the importance of different dissemination requirements by different weights in the generalized models that are developed.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2021
- Source ID
- FA95502010080
Entities
People
- Ramamoorthi Ravi
Organizations
- Air Force Office of Scientific Research
- Carnegie Mellon University
- United States Air Force