Brief Announcement: Minimizing the Weighted Average Shortest Path Length in Demand-Aware Networks via Matching Augmentation

Graph augmentation is a fundamental and well-studied problem that arises in network optimization. We consider a new variant of this model motivated by reconfigurable communication networks. In this variant, we differentiate between a given physical network and the measured communication demands between the nodes. Our goal is to minimize the weighted average shortest path length via matching augmentation, where the weights correspond to the communication frequency of any pair of nodes. We use results from demand-Aware network design to provide a constant-factor approximation algorithm for adding a matching on a ring in case only a few nodes in the network cause almost all the communication. Since the problem is NP-hard, we design and evaluate a series of heuristics that can deal with arbitrary graphs as underlying network structures. We evaluate our heuristics on general real-world communication patterns and show that already with simple and efficient heuristics we are able to reach near-optimal quality.