{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T22:45:48Z","timestamp":1753051548605},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,5]]},"abstract":"<jats:p>\n            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\n            <jats:italic>noticeable<\/jats:italic>\n            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\n            <jats:italic>k<\/jats:italic>\n            network upgrades such that it maximizes the number of flows in the network with a\n            <jats:italic>noticeable<\/jats:italic>\n            reduction in delay. We show that the problem is NP-hard, APX-hard, and non-submodular. We overcome these computational challenges by designing an\n            <jats:italic>importance sampling<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.14778\/3213880.3213889","type":"journal-article","created":{"date-parts":[[2018,6,12]],"date-time":"2018-06-12T18:15:11Z","timestamp":1528827311000},"page":"988-1001","source":"Crossref","is-referenced-by-count":9,"title":["Noticeable network delay minimization via node upgrades"],"prefix":"10.14778","volume":"11","author":[{"given":"Sourav","family":"Medya","sequence":"first","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sayan","family":"Ranu","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Delhi"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jithin","family":"Vachery","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology, Madras"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ambuj","family":"Singh","sequence":"additional","affiliation":[{"name":"University of California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-69033-9","volume-title":"Stochastic simulation: algorithms and analysis","author":"Asmussen S.","year":"2007"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2014.41"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939846"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187908"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20086-6_4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2953882"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13731-0_39"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2009680.2009689"},{"key":"e_1_2_1_9_1","volume-title":"New york city taxi trip data (2010-2013)","author":"Donovan D.","year":"2016"},{"key":"e_1_2_1_10_1","volume-title":"ACM","author":"Garg N.","year":"2018"},{"key":"e_1_2_1_11_1","volume-title":"Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13--30","author":"Hoeffding W.","year":"1963"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.37"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/COMSNETS.2014.6734912"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009798010579"},{"key":"e_1_2_1_15_1","article-title":"A hierarchical framework for intelligent traffic management in smart cities","author":"Li Z.","year":"2017","journal-title":"IEEE Transactions on Smart Grid, PP(99):1--1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-014-0219-1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850578.2850581"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939869"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0140"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975321.14"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_21"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218449"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys2535"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.3.177"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230260105"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063952"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/MILCOM.2013.319"},{"key":"e_1_2_1_29_1","volume-title":"CRAWDAD dataset epfl\/mobility (v. 2009-02-24). Downloaded from http:\/\/crawdad.org\/epfl\/mobility\/200 9022","author":"Piorkowski M.","year":"2009"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556195.2556224"},{"key":"e_1_2_1_31_1","volume-title":"2015 urban mobility scorecard and appendices","author":"Schrank D."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113347"},{"key":"e_1_2_1_33_1","first-page":"1341","volume-title":"AAMAS","author":"Waniek M.","year":"2017"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithms","author":"Williamson D. P.","year":"2011"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623626"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1869790.1869807"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3213880.3213889","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:01:38Z","timestamp":1672221698000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3213880.3213889"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,5]]},"references-count":36,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["10.14778\/3213880.3213889"],"URL":"https:\/\/doi.org\/10.14778\/3213880.3213889","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,5]]}}}