Noticeable Network Delay Minimization via Node Upgrades

Summary: Introduces a k-upgrade network design to maximize flows with noticeable delay reductions, prioritizing important nodes. NP-hard, APX-hard, non-submodular; an importance-sampling algorithm with guarantees yields up to 1000x speed-up over greedy and 70x over prior work, validated on real and synthetic data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 11800
Venue: VLDB
Year: 2018
Pagerank: 4.456315e-05
Overall Rank: 8,761 | 39.06%
DOI: 10.14778/3213880.3213889

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,141	Expanding Reverse Nearest Neighbors	2024	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2,371	From Competition to Complementarity: Comparative Influence Diffusion and Maximization	2016	VLDB	8.9482922e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,006	Last-Mile Delivery Made Practical: An Efficient Route Planning Framework with Theoretical Guarantees	2020	VLDB	5.2415551e-05
4,193	Relative Subboundedness of Contraction Hierarchy and Hierarchical 2-Hop Index in Dynamic Road Networks	2022	SIGMOD	6.37019e-05
9,679	Real-time Insertion Operator for Shared Mobility on Time-Dependent Road Networks	2024	VLDB	4.3047774e-05
14,302	An Approximation Algorithm To The File Allocation Problem In Computer Networks	1983	PODS	-
6,171	Shortest Paths and Centrality in Uncertain Networks	2021	VLDB	5.170101e-05
12,494	Quality-Aware Distributed Data Delivery for Continuous Query Services	2006	SIGMOD	4.1945683e-05
8,907	Shortest Paths Discovery in Uncertain Networks via Transfer Learning	2023	SIGMOD	4.427232e-05
12,154	The Filter-Placement Problem and its Application to Minimizing Information Multiplicity	2012	VLDB	4.1945683e-05
6,494	An Experimental Evaluation and Guideline for Path Finding in Weighted Dynamic Network	2021	VLDB	5.0417258e-05
6,814	Efficient Algorithms for Optimal Location Queries in Road Networks	2014	SIGMOD	4.9185216e-05