{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:34Z","timestamp":1787340574175,"version":"build-2736575974"},"reference-count":11,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,11]]},"abstract":"<jats:p>In computer networks, message routing is often accomplished by network nodes using local information. The unavailability of global information intuitively makes hard routing problems virtually impossible. This paper formalizes this intuition by examining a hard (NP-complete) routing problem, the problem of multi-destination routing. It is shown that with only limited information it is impossible to optimize network utilization for the multi-destination routing problem. Moreover, it is impossible to even approximate optimality to within a specific tolerance. Several versions of this result are proved; the versions differ in terms of the amount of information available at a node, and the extent to which the problem cannot be approximated. An improved local information algorithm is presented which is best possible amongst local information algorithms.<\/jats:p>","DOI":"10.1137\/0214062","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"875-888","source":"Crossref","is-referenced-by-count":18,"title":["Distributed Multi-Destination Routing: The Constraints of Local Information"],"prefix":"10.1137","volume":"14","author":[{"given":"Jeffrey M.","family":"Jaffe","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","volume-title":"Computer Communication Network Design and Analysis","author":"Schwartz M.","year":"1977"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/359657.359665"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1983.1095818"},{"key":"R4","unstructured":"D. Wall, Ph.D. Thesis, Stanford Univ., Stanford, CA,  1980"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"D. Angluin,  Local and global properties in networks of processors,  Proc. Twelfth Annual ACM Sythposium on Theory of Computing,  1980,  82\u201393","DOI":"10.1145\/800141.804655"},{"key":"R7","unstructured":"S. R. Soloway,  On the node-numbering problem,  Proc. Eighteenth Annual Allerton Conference on Communication, Control, and Computing,  1979,  514\u2013523"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1981.1095152"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322284"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1980.1094690"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1978.1094040"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214062","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:58Z","timestamp":1787337598000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214062"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,11]]},"references-count":11,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1985,11]]}},"alternative-id":["10.1137\/0214062"],"URL":"https:\/\/doi.org\/10.1137\/0214062","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,11]]}}}