{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:27:58Z","timestamp":1759667278052},"reference-count":27,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7710,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1985,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Previous work has shown the budget network design problem (selecting a subset of arcs, subject to a budget constraint, so that the total weighted sum of the shortest paths in the network is minimized) to be a very difficult optimization problem. This article gives an efficient heuristic procedure for solving budget network design problems embedded in a circle on the euclidean plane where the nodes are independently and randomly distributed over the circle. With mild conditions on the budget constraint, we prove that as the number of nodes increases, the probability that the heuristic solution value exceeds any fixed percentage of the optimal solution value goes to zero. Computational results for the heuristic arc given.<\/jats:p>","DOI":"10.1002\/net.3230150306","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T19:51:06Z","timestamp":1178913066000},"page":"347-363","source":"Crossref","is-referenced-by-count":7,"title":["Probabilistic analysis of a network design problem heuristic"],"prefix":"10.1002","volume":"15","author":[{"given":"Richard T.","family":"Wong","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90012-8"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034095"},{"key":"e_1_2_1_4_2","unstructured":"Z.Berkowitz Contributions to the solution of the optimal network design problem. Masters Thesis Department of Statistics and Operations Research University of South Africa (1982)."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1068\/a050519"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01583791"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.28.4.847"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230090104"},{"key":"e_1_2_1_9_2","volume-title":"Distribution Management","author":"Eilon S.","year":"1971"},{"key":"e_1_2_1_10_2","volume-title":"An Introduction to Probability Theory and its Applications, Vol. I","author":"Feller W.","year":"1968"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.5.1.27"},{"key":"e_1_2_1_12_2","volume-title":"Algorithms and Complexity","author":"Garey M. R.","year":"1976"},{"key":"e_1_2_1_13_2","unstructured":"M.Haimovich Asymptotic properties of geometric location problems. Doctoral Dissertation Department of Aeronautics and Astronautics Massachusetts Institute of Technology (1984)."},{"key":"e_1_2_1_14_2","article-title":"Bounds and heuristics for capacitated routing problems","author":"Haimovich M.","journal-title":"Math. Opns. Res."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.19.5.488"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.2307\/1426733"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080402"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2.3.209"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208045"},{"key":"e_1_2_1_20_2","volume-title":"Queueing Systems Volume 1: Theory","author":"Kleinrock L.","year":"1975"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.18.1.1"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230080306"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210040"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0041-1647(69)90152-X"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176994411"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.6.3.374"},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.3.2.89"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/0601008"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230150306","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230150306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T12:55:43Z","timestamp":1697806543000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230150306"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,9]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,9]]}},"alternative-id":["10.1002\/net.3230150306"],"URL":"https:\/\/doi.org\/10.1002\/net.3230150306","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,9]]}}}