Bicriteria Network Design Problems
Abstract
Complex networks are fundamentally optimized for multiple objectives, such as having both low congestion and low latency. We propose the study of three basic network design problems that involve two criteria- diameter bounded MSTs in undirected graphs, and subgraphs with low degree and diameter connecting a set of terminal pairs in undirected graphs and a subset of terminals in digraphs. All three problems arise in low latency communication problems- the former is the simplest formulation of the cheapest connector with the lowest hop latency; the two latter problems arise in fast information dissemination problems. The main goal of this project is to develop provably near-optimal approximation algorithms for bicriteria network design problems involving low latency networks. The proposed research will investigate several strategies for deriving such algorithms such as rounding linear programming relaxations and greedy augmentation methods. A key outcome of our work will be the design of better subgraphs for low latency information flow in arbitrary networks, and potentially new techniques for deriving bicriteria approximation algorithms for network design.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 22, 2024
- Source ID
- FA95502310031
Entities
People
- Ramamoorthi Ravi
Organizations
- Air Force Office of Scientific Research
- Carnegie Mellon University
- United States Air Force