{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T05:15:10Z","timestamp":1768540510819,"version":"3.49.0"},"reference-count":67,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2009,2,13]],"date-time":"2009-02-13T00:00:00Z","timestamp":1234483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this article, we discuss the relation of unsplittable shortest path routing (USPR) to other routing schemes and study the approximability of three USPR network planning problems. Given a digraph<jats:italic>D<\/jats:italic>= (<jats:italic>V<\/jats:italic>,<jats:italic>A<\/jats:italic>) and a set<jats:italic>K<\/jats:italic>of directed commodities, an USPR is a set of flow paths<jats:italic>P<\/jats:italic><jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/tex2gif-stack-1.gif\" xlink:title=\"urn:x-wiley:00283045:media:NET20303:tex2gif-stack-1\"\/>, (<jats:italic>s<\/jats:italic>,<jats:italic>t<\/jats:italic>) \u2208<jats:italic>K<\/jats:italic>, such that there exists a metric \u03bb = (\u03bb<jats:sub><jats:italic>a<\/jats:italic><\/jats:sub>) \u2208<jats:italic>Z<\/jats:italic><jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/tex2gif-stack-2.gif\" xlink:title=\"urn:x-wiley:00283045:media:NET20303:tex2gif-stack-2\"\/>with respect to which each<jats:italic>P<\/jats:italic><jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/tex2gif-stack-3.gif\" xlink:title=\"urn:x-wiley:00283045:media:NET20303:tex2gif-stack-3\"\/>is the unique shortest (<jats:italic>s<\/jats:italic>,<jats:italic>t<\/jats:italic>)\u2010path. In the Min\u2010Con\u2010USPR problem, we seek an USPR that minimizes the maximum congestion over all arcs. We show that this problem is NP\u2010hard to approximate within a factor of<jats:italic>O<\/jats:italic>(|<jats:italic>V<\/jats:italic>|<jats:sup>1\u2212\u03f5<\/jats:sup>), but polynomially approximable within min(|<jats:italic>A<\/jats:italic>|,|<jats:italic>K<\/jats:italic>|) in general and within<jats:italic>O<\/jats:italic>(1) if the underlying graph is an undirected cycle or a bidirected ring. We also construct examples where the minimum congestion that can be obtained by USPR is a factor of \u03a9(|<jats:italic>V<\/jats:italic>|<jats:sup>2<\/jats:sup>) larger than that achievable by unsplittable flow routing or by shortest multipath routing, and a factor of \u03a9(|<jats:italic>V<\/jats:italic>|) larger than that achievable by unsplittable source\u2010invariant routing. In the C<jats:sc>AP<\/jats:sc>\u2010USPR problem, we seek a minimum cost installation of integer arc capacities that admit an USPR of the given commodities. We prove that this problem is NP\u2010hard to approximate within 2 \u2212 \u03f5 even in the undirected case, and we devise approximation algorithms for various special cases. The fixed charge network design problem FC\u2010USPR, where the task is to find a minimum cost subgraph of<jats:italic>D<\/jats:italic>whose fixed arc capacities admit an USPR of the commodities, is shown to be NPO\u2010complete. All three problems are of great practical interest in the planning of telecommunication networks that are based on shortest path routing protocols. Our results indicate that they are harder than the corresponding unsplittable flow or shortest multi\u2010path routing problems. \u00a9 2009 Wiley Periodicals, Inc. NETWORKS, 2009<\/jats:p>","DOI":"10.1002\/net.20303","type":"journal-article","created":{"date-parts":[[2009,2,13]],"date-time":"2009-02-13T16:38:18Z","timestamp":1234543098000},"page":"23-46","source":"Crossref","is-referenced-by-count":20,"title":["Approximability of unsplittable shortest path routing problems"],"prefix":"10.1002","volume":"54","author":[{"given":"Andreas","family":"Bley","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2009,2,13]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"M.Andrews Hardness of buy\u2010at\u2010bulk network design Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science Rome Italy 2004 pp.115\u2013124.","DOI":"10.1109\/FOCS.2004.32"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"B.AwerbuchandY.Azar Buy\u2010at\u2010bulk network design Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science Miami Beach FL 1997 pp.542\u2013547.","DOI":"10.1109\/SFCS.1997.646143"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"Y.Bartal On approximating arbitrary metrics by tree metrics Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing Dallas TX 1998 pp.161\u2013168.","DOI":"10.1145\/276698.276725"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1002\/dac.551"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480100377428"},{"key":"e_1_2_1_8_2","unstructured":"W.Ben\u2010Ameur E.Gourdin B.Liau andN.Michel Optimizing administrative weights for efficient single\u2010path routing Proc Networks 2000 Toronto Canada 2000."},{"key":"e_1_2_1_9_2","unstructured":"A.Bley A Lagrangian approach for integrated network design and routing in IP networks Proceedings of the 1st International Network Optimization Conference (INOC 2003) Paris France 2003 pp.107\u2013113."},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"A.Bley On the approximability of the minimum congestion unsplittable shortest path routing problem Proceedings of the 11th Conference on Integer Programming and Combinatorial Optimization (IPCO 2005) Berlin Germany (Berlin) June2005 pp.97\u2013110.","DOI":"10.1007\/11496915_8"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.20163"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"A.Bley Routing and capacity optimization for IP networks Proceedings of Operations Research 2007 Saarbr\u00fccken Germany 2007 pp.9\u201316.","DOI":"10.1007\/978-3-540-77903-2_2"},{"key":"e_1_2_1_13_2","unstructured":"A.Bley Routing and capacity optimization for IP networks PhD thesis Technische Universit\u00e4t(2007)."},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"A.Bley An integer programming algorithm for routing optimization in IP networks Proceedings of 16th Annual European Symposium on Algorithms (ESA 2008) Karlsruhe Germany 2008 pp.198\u2013209.","DOI":"10.1007\/978-3-540-87744-8_17"},{"key":"e_1_2_1_15_2","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"1","volume-title":"Robust communication networks: Interconnection and survivability","author":"Bley A.","year":"1998"},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"A.BleyandT.Koch Integer programming approaches to access and backbone IP\u2010network planning Proceedings of 3rd International Conference on High Performance Scientific Computing Hanoi Vietnam 2006 pp.87\u2013110.","DOI":"10.1007\/978-3-540-79409-7_7"},{"key":"e_1_2_1_17_2","unstructured":"N.Bourquia W.Ben\u2010Ameur E.Gourdin andP.Tolla Optimal shortest path routing for Internet networks Proceedings of the 1st International Network Optimization Conference (INOC 2003) Paris France 2003 pp.119\u2013125."},{"key":"e_1_2_1_18_2","unstructured":"P.Brostr\u00f6m Optimization in the design of OSPF telecommunication networks Ph.D. thesis Link\u00f6ping University 2004."},{"key":"e_1_2_1_19_2","unstructured":"P.Brostr\u00f6mandK.Holmberg \u201cDetermining the non\u2010existence of compatible OSPF weights \u201d Nordic MPS 2004 D. Yuan (Editor) Link\u00f6ping Electronic Conference Proceedings No. 14 Link\u00f6ping University Electronic Press 2004 pp.7\u201321."},{"key":"e_1_2_1_20_2","unstructured":"P.Brostr\u00f6mandK.Holmberg Stronger necessary conditions for the existence of a compatible OSPF metric Technical Report LiTH\u2010MAT\u2010R\u20102004\u201008 Link\u00f6ping University (May2004)."},{"key":"e_1_2_1_21_2","unstructured":"P.Brostr\u00f6mandK.Holmberg Design of IP\/OSPF networks using a Lagrangean heuristic on an in\u2010graph based model Proceedings of the 2nd International Network Optimization Conference (INOC 2005) Lisbon Portugal 2005 pp.702\u2013709."},{"key":"e_1_2_1_22_2","unstructured":"P.Brostr\u00f6mandK.Holmberg Compatible weights and valid cycles in non\u2010spanning OSPF routing patterns Research Report LiTH\u2010MAT\u2010R\u20102007\u201004 Department of Mathematics Link\u00f6ping Institute of Technology Sweden 2007."},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.20070"},{"key":"e_1_2_1_24_2","doi-asserted-by":"crossref","unstructured":"R.Callon Use of OSI IS\u2010IS for routing in TCP\/IP and dual environments IETF Internet RFC 1195 December1990.","DOI":"10.17487\/rfc1195"},{"key":"e_1_2_1_25_2","unstructured":"M.Charikar C.Chekuri T.Cheung Z.Dai A.Goel S.Guha andM.Li Approximation algorithms for directed steiner problems Proceedings of the ACM\u2010SIAM Symposium on Discrete Algorithms 1998 San Francisco CA 1998 pp.192\u2013200."},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"M.Charikar C.Chekuri A.Goel S.Guha andS.A.Plotkin Approximating a finite metric by a small number of tree metrics Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science Palo Alto CA 1998 pp.379\u2013388.","DOI":"10.1109\/SFCS.1998.743488"},{"key":"e_1_2_1_27_2","doi-asserted-by":"crossref","unstructured":"M.CharikarandA.Karagiozova On non\u2010uniform multicommodity buy\u2010at\u2010bulk network design Proceedings of the Thirty\u2010seventh Annual ACM Symposium on the Theory of Computing Baltimore Maryland 2005 pp.176\u2013182.","DOI":"10.1145\/1060590.1060617"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02110141"},{"key":"e_1_2_1_29_2","unstructured":"P.CrescenziandV.Kann A compendium of NP optimization problems webpage.https:\/\/2.zoppoz.workers.dev:443\/http\/www.nada.kth.se\/\u223cviggo\/problemlist\/compendium.html."},{"key":"e_1_2_1_30_2","unstructured":"L.de Giovanni B.Fortz andM.Labb\u00e9 A lower bound for the Internet protocol network design problem Proceedings of the 2nd International Network Optimization Conference (INOC 2005) Lisbon Portugal 2005 pp.402\u2013408."},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050043"},{"key":"e_1_2_1_32_2","doi-asserted-by":"crossref","unstructured":"Y.DodisandS.Khanna Designing networks with bounded pairwise distance Proceedings of the Thirty\u2010first Annual ACM Symposium on the Theory of Computing Atlanta GA 1999 pp.750\u2013759.","DOI":"10.1145\/301250.301447"},{"key":"e_1_2_1_33_2","first-page":"251","article-title":"Regu\u00e4re Graphen gegebener Taillenweite mit minimaler Knotenzahl","volume":"12","author":"Erd\u00f6s P.","year":"1963","journal-title":"Wissenschaftliche Zeitung der Universit\u00e4t Halle\u2010Wittenberg"},{"key":"e_1_2_1_34_2","unstructured":"A.Eremin F.Ajili andR.Rodosek A set\u2010based approach to the optimal IGP weight setting problem Proceedings of the 2nd International Network Optimization Conference (INOC 2005) Lisbon Portugal 2005 pp.386\u2013392."},{"key":"e_1_2_1_35_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1014852026591"},{"key":"e_1_2_1_36_2","doi-asserted-by":"crossref","unstructured":"J.Fakcharoenphol S.Rao andK.Talwar A tight bound on approximating arbitrary metrics by tree metrics Proceedings of the Thirty\u2010fifth Annual ACM Symposium on the Theory of Computing San Diego CA 2003 pp.448\u2013455.","DOI":"10.1145\/780542.780608"},{"key":"e_1_2_1_37_2","unstructured":"A.Farago A.Szentesi andB.Szviatovszki Allocation of administrative weights in PNNI Proceedings of Networks '98 Sorrento Italy 1998 pp.621\u2013625."},{"key":"e_1_2_1_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00235-4"},{"key":"e_1_2_1_39_2","doi-asserted-by":"crossref","unstructured":"B.FortzandM.Thorup Internet traffic engineering by optimizing OSPF weights Proceedings of the 19th IEEE Infocom 2000 Tel\u2010Aviv Israel 2000 pp.519\u2013528.","DOI":"10.1109\/INFCOM.2000.832225"},{"key":"e_1_2_1_40_2","unstructured":"B.FortzandM.Thorup Robust optimization of OSPF\/IS\u2010IS weights Proceedings of the 1st International Network Optimization Conference (INOC 2003) Paris France 2003 pp.225\u2013230."},{"key":"e_1_2_1_41_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:COAP.0000039487.35027.02"},{"key":"e_1_2_1_42_2","volume-title":"Computers and intractability: A guide to the theory of NP\u2010completeness","author":"Garey M.","year":"1979"},{"key":"e_1_2_1_43_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_44_2","unstructured":"E.Gourdin Optimizing Internet networks OR\/MS Today 2001 46\u201349."},{"key":"e_1_2_1_45_2","doi-asserted-by":"crossref","unstructured":"S.Guha A.Meyerson andK.Munagala A constant factor approximation for the single sink edge installation problem Proceedings of the Thirty\u2010third Annual ACM Symposium on the Theory of Computing Hersonissos Crete Greece 2001 pp.383\u2013388.","DOI":"10.1145\/380752.380827"},{"key":"e_1_2_1_46_2","doi-asserted-by":"crossref","unstructured":"A.Gupta A.Kumar andT.Roughgarden Simpler and better approximation algorithms for network design Proceedings of the Thirty\u2010fifth Annual ACM Symposium on the Theory of Computing San Diego CA 2003 pp.365\u2013372.","DOI":"10.1145\/780542.780597"},{"key":"e_1_2_1_47_2","doi-asserted-by":"crossref","unstructured":"C.Hedrick Routing information protocol IETF Internet RFC 1058 June1988.","DOI":"10.17487\/rfc1058"},{"key":"e_1_2_1_48_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.10102"},{"key":"e_1_2_1_49_2","unstructured":"A.J\u00fcttner A.Szentesi J.Harmatos andM.Pi\u00f3ro On solvability of an ospf routing problem 15th Nordic Teletraffic Seminar Lund Sweden 2000 pp.1\u20139."},{"key":"e_1_2_1_50_2","unstructured":"V.KaibelandM.Peinhardt On the bottleneck shortest path problem Tech. Report ZR\u201006\u201022 Konrad\u2010Zuse\u2010Zentrum f\u00fcr Informationstechnik(2006)."},{"key":"e_1_2_1_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_2_1_52_2","doi-asserted-by":"crossref","unstructured":"S.KolliopoulosandC.Stein Improved approximation algorithms for unsplittable flow problems Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science Miami Beach FL 1997 pp.426\u2013435.","DOI":"10.1109\/SFCS.1997.646131"},{"key":"e_1_2_1_53_2","doi-asserted-by":"crossref","unstructured":"F.LinandJ.Wang Minimax open shortest path first routing algorithms in networks supporting the SMDS service Proceedings of the IEEE International Conference on Communications 1993 (ICC'93) Geneva Suisse vol. 2 1993 pp.666\u2013670.","DOI":"10.1109\/ICC.1993.397358"},{"key":"e_1_2_1_54_2","unstructured":"D.Lorenz A.Orda D.Raz andY.Shavitt How good can IP routing be? Technical Report 2001\u201017 DIMACS Center for Discrete Mathematics and Theoretical Computer Science Rutgers University Princeton University AT&T Bell Laboratries and Bellcore(2001)."},{"key":"e_1_2_1_55_2","unstructured":"Y.MansurandD.Peleg An approximation algorithm for minimum\u2010cost network design Tech. Report CS94\u201022 Weizmann Institute of Science Rehovot Israel 1994."},{"key":"e_1_2_1_56_2","doi-asserted-by":"crossref","unstructured":"A.Meyerson K.Munagala andS.Plotkin Cost\u2010distance: Two\u2010metric network design Proceedings of the Thirty\u2010second Annual ACM Symposium on the Theory of Computing Portland OR 2000 pp.624\u2013630.","DOI":"10.1109\/SFCS.2000.892330"},{"key":"e_1_2_1_57_2","doi-asserted-by":"crossref","unstructured":"J.Moy OSPF version 2 IETF Internet RFC 2328 April1998.","DOI":"10.17487\/rfc2328"},{"key":"e_1_2_1_58_2","unstructured":"P.OrponenandH.Mannila On approximation preserving reductions: Complete problems and robust measures Technical Report C\u20101987\u201028 Department of Computer Science University of Helsinki 1987."},{"key":"e_1_2_1_59_2","unstructured":"A.Parmar S.Ahmed andJ.Sokol An integer programming approach to the OSPF weight setting problem Optimization Online 2006."},{"key":"e_1_2_1_60_2","volume-title":"Routing, flow, and capacity design in communication and computer networks","author":"Pi\u00f3ro M.","year":"2004"},{"key":"e_1_2_1_61_2","unstructured":"M.Pi\u00f3ro A.Szentesi J.Harmatos andA.J\u00fcttner On OSPF related network optimization problems 8th IFIP Workshop on Performance Modelling and Evaluation of ATM & IP Networks Ilkley UK 2000 pp.70\/1\u201370\/14."},{"key":"e_1_2_1_62_2","unstructured":"M.Prytz On optimization in design of telecommunications networks with multicast and unicast traffic Ph.D. thesis Royal Institute of Technology Stockholm Sweden 2002."},{"key":"e_1_2_1_63_2","unstructured":"F.S.Salman J.Cheriyan R.Ravi andS.Subramanian Buy\u2010at\u2010bulk network design: Approximating the single\u2010sink edge installation problem Proceedings of the 8th ACM\u2010SIAM Symposium on Discrete Algorithms New Orleans LA 1997 pp.619\u2013628."},{"key":"e_1_2_1_64_2","first-page":"1","article-title":"The ring loading problem","volume":"11","author":"Schrijver A.","year":"1998","journal-title":"SIAM J Appl Math"},{"key":"e_1_2_1_65_2","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100260"},{"key":"e_1_2_1_66_2","doi-asserted-by":"crossref","unstructured":"K.Talwar Single\u2010sink buy\u2010at\u2010bulk LP has constant integrality gap Proceedings of the 9th Conference on Integer Programming and Combinatorial Optimization (IPCO 2002) Cambridge MA 2002 pp.475\u2013486.","DOI":"10.1007\/3-540-47867-1_33"},{"key":"e_1_2_1_67_2","unstructured":"A.Tomaszewski M.Pi\u00f3ro M.Dzida andM.Zago\u017cd\u017con Optimization of administrative weights in IP networks using the branch\u2010and\u2010cut approach Proceedings of the 2nd International Network Optimization Conference (INOC 2005) Lisbon Portugal 2005 pp.393\u2013400."},{"key":"e_1_2_1_68_2","unstructured":"H.\u00dcmitandB.Fortz Fast heuristic techniques for intra\u2010domain routing metric optimization Proceedings of the 3rd International Network Optimization Conference (INOC 2007) Spa Belgium 2007."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.20303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.20303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T18:16:44Z","timestamp":1738952204000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/10.1002\/net.20303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,13]]},"references-count":67,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1002\/net.20303"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/net.20303","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2,13]]}}}