Noticeable network delay minimization via node upgrades

Sourav Medya*, Jithin Vachery, Sayan Ranu, Ambuj Singh

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

11 Scopus citations


In several domains, the flow of data is governed by an underlying network. Reduction of delays in end-to-end data flow is an important network optimization task. Reduced delays enable shorter travel times for vehicles in road networks, faster information flow in social networks, and increased rate of packets in communication networks. While techniques for network delay minimization have been proposed, they fail to provide any noticeable reduction in individual data flows. Furthermore, they treat all nodes as equally important, which is often not the case in real-world networks. In this paper, we incorporate these practical aspects and propose a network design problem where the goal is to perform k network upgrades such that it maximizes the number of flows in the network with a noticeable reduction in delay. We show that the problem is NP-hard, APX-hard, and non-submodular. We overcome these computational challenges by designing an importance sampling based algorithm with provable quality guarantees. Through extensive experiments on real and synthetic data sets, we establish that importance sampling imparts up to 1000 times speed-up over the greedy approach, and provides up to 70 times the improvement achieved by the state-of-the-art technique.

Original languageEnglish (US)
Pages (from-to)988-1001
Number of pages14
JournalProceedings of the VLDB Endowment
Issue number9
StatePublished - 2018
Externally publishedYes
Event44th International Conference on Very Large Data Bases, VLDB 2018 - Rio de Janeiro, Brazil
Duration: Aug 27 2018Aug 31 2018

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • General Computer Science


Dive into the research topics of 'Noticeable network delay minimization via node upgrades'. Together they form a unique fingerprint.

Cite this