Towards scalable network delay minimization

Sourav Medya, Petko Bogdanov, Ambuj Singh

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


Reduction of end-To-end network delays is an optimization task with applications in multiple domains. Low delays enable improved information flow in social networks, quick spread of ideas in collaboration networks, low travel times for vehicles on road networks and increased rate of packets in communication networks. Delay reduction can be achieved by both improving the propagation capabilities of individual nodes and adding additional edges in the network. One of the main challenges in such design problems is that the effects of local changes are not independent, and as a consequence, there is a combinatorial search space of possible improvements. Thus, minimizing the cumulative propagation delay requires novel scalable and data-driven approaches. In this paper, we consider the problem of network delay minimization via node upgrades. Although the problem is NPhard, we show that probabilistic approximation for a restricted version can be obtained. We design scalable and high-quality techniques for the general setting based on sampling that are targeted to different models of delay distribution. Our methods scale almost linearly with the graph size and consistently outperform competitors in quality.

Original languageEnglish (US)
Title of host publicationProceedings - 16th IEEE International Conference on Data Mining, ICDM 2016
EditorsFrancesco Bonchi, Josep Domingo-Ferrer, Ricardo Baeza-Yates, Zhi-Hua Zhou, Xindong Wu
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781509054725
StatePublished - Jul 2 2016
Externally publishedYes
Event16th IEEE International Conference on Data Mining, ICDM 2016 - Barcelona, Catalonia, Spain
Duration: Dec 12 2016Dec 15 2016

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786


Other16th IEEE International Conference on Data Mining, ICDM 2016
CityBarcelona, Catalonia

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'Towards scalable network delay minimization'. Together they form a unique fingerprint.

Cite this