{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T09:43:23Z","timestamp":1697017403520},"reference-count":25,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T00:00:00Z","timestamp":1369699200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"funder":[{"name":"National Science Center (Poland); Integer programming models for joint optimization of link capacity assignment, transmission scheduling, and routing in fair multicommodity flow networks","award":["2011\/01\/B\/ST7\/02967"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2013,9]]},"abstract":"Abstract<\/jats:title>In this article, we revisit a classical optimization problem occurring in designing survivable multicommodity flow networks. The problem, referred to as FR, assumes flow restoration that takes advantage of the so\u2010called stub release. As no compact linear programming (LP) formulation of FR is known and at the same time all known noncompact LP formulations of FR exhibit\n\\documentclass{article}\\usepackage{mathrsfs}\\usepackage{amsmath}\\pagestyle{empty}\\begin{document}\\begin{align*}\\mathcal{NP}\\end{align*} \\end{document}<\/jats:styled-content>\n\u2010hard dual separation, the problem itself is believed to be\n\\documentclass{article}\\usepackage{mathrsfs}\\usepackage{amsmath}\\pagestyle{empty}\\begin{document}\\begin{align*}\\mathcal{NP}\\end{align*} \\end{document}<\/jats:styled-content>\n\u2010hard, although without a proof. In this article, we study a restriction of FR (RFR) that assumes only elementary (cycle\u2010free) admissible paths\u2014an important case virtually not considered in the literature. The two problems have the same noncompact LP formulations as they differ only in the definition of admissible paths: all paths (also those including cycles) are allowed in FR, while only elementary paths are allowed in RFR. Because of that, RFR is in general computationally more complex than FR. The purpose of this article, is three\u2010fold. First, the article reveals an interesting special case of RFR\u2014the case with only one failing link\u2014for which a natural noncompact LP formulation obtained by reducing the general RFR formulation still exhibits\n\\documentclass{article}\\usepackage{mathrsfs}\\usepackage{amsmath}\\pagestyle{empty}\\begin{document}\\begin{align*}\\mathcal{NP}\\end{align*} \\end{document}<\/jats:styled-content>\n\u2010hard dual separation, but nevertheless this special case of RFR is polynomial. The constructed example of a polynomial multicommodity flow problem with difficult dual separation is of interest since, to our knowledge, no example of this kind has been known. In this article, we also examine a second special case of RFR, this time assuming two failing links instead of one, which turns out to be\n\\documentclass{article}\\usepackage{mathrsfs}\\usepackage{amsmath}\\pagestyle{empty}\\begin{document}\\begin{align*}\\mathcal{NP}\\end{align*} \\end{document}<\/jats:styled-content>\n\u2010hard. This implies that problem RFR is\n\\documentclass{article}\\usepackage{mathrsfs}\\usepackage{amsmath}\\pagestyle{empty}\\begin{document}\\begin{align*}\\mathcal{NP}\\end{align*} \\end{document}<\/jats:styled-content>\n\u2010hard in general (more precisely, for two or more failure states). This new result is the second contribution of the article. Finally, we discuss the complexity of FR in the light of our new findings, emphasizing the differences between RFR and FR. \u00a9 2013 Wiley Periodicals, Inc. NETWORKS, 2013<\/jats:p>","DOI":"10.1002\/net.21508","type":"journal-article","created":{"date-parts":[[2013,5,28]],"date-time":"2013-05-28T14:11:16Z","timestamp":1369750276000},"page":"149-160","source":"Crossref","is-referenced-by-count":6,"title":["Complexity of a classical flow restoration problem"],"prefix":"10.1002","volume":"62","author":[{"given":"Dritan","family":"Nace","sequence":"first","affiliation":[]},{"given":"Micha\u0142","family":"Pi\u00f3ro","sequence":"additional","affiliation":[]},{"given":"Artur","family":"Tomaszewski","sequence":"additional","affiliation":[]},{"given":"Mateusz","family":"\u017botkiewicz","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2013,5,28]]},"reference":[{"key":"e_1_2_8_2_2","volume-title":"Network flows: Theory, algorithms, and applications","author":"Ahuja R.K.","year":"1993"},{"key":"e_1_2_8_3_2","series-title":"LNCS, Vol. 5275, Proc 8th IEEE Int Workshop IP Oper Manage (IPOM'08)","first-page":"66","author":"Bashllari A.","year":"2008"},{"key":"e_1_2_8_4_2","series-title":"Proc 3rd Int Network Optimization Conference (INOC 2007)","author":"Bashllari A.","year":"2007"},{"key":"e_1_2_8_5_2","volume-title":"Survivable networks\u2014Algorithms for diverse routing","author":"Bhandari R.","year":"1999"},{"key":"e_1_2_8_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.10.1.1"},{"key":"e_1_2_8_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00121-2"},{"key":"e_1_2_8_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90009-2"},{"key":"e_1_2_8_9_2","volume-title":"Computers and intractability: A guide to the theory of NP\u2010completeness","author":"Garey M.R.","year":"1979"},{"key":"e_1_2_8_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97881-4"},{"key":"e_1_2_8_11_2","first-page":"53","article-title":"Network synthesis under survivability constraints","volume":"2","author":"Maurras J.\u2010F.","year":"2004","journal-title":"4OR"},{"key":"e_1_2_8_12_2","series-title":"Proc 7th Int Workshop Design Reliable Commun Networks (DRCN 2009)","first-page":"273","author":"Mereu A.","year":"2009"},{"key":"e_1_2_8_13_2","volume-title":"OSPF version 2, Internet RFC 2328","author":"Moy J.","year":"1998"},{"key":"e_1_2_8_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/90.664269"},{"key":"e_1_2_8_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372"},{"key":"e_1_2_8_16_2","volume-title":"Local and global restoration of node and link failures in telecommunication networks","author":"Orlowski S.","year":"2003"},{"key":"e_1_2_8_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.20484"},{"key":"e_1_2_8_18_2","volume-title":"Routing, flow, and capacity design in communication and computer networks","author":"Pi\u00f3ro M.","year":"2004"},{"key":"e_1_2_8_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30165-5"},{"key":"e_1_2_8_20_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_8_21_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792224061"},{"key":"e_1_2_8_22_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230040204"},{"key":"e_1_2_8_23_2","series-title":"To appear in Proc 6th Int Network Optim Conf (INOC 2013)","author":"Tomaszewski A.","year":"2013"},{"key":"e_1_2_8_24_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.20321"},{"key":"e_1_2_8_25_2","volume-title":"Dimensioning survivable capacitated networks","author":"Wess\u00e4ly R.","year":"2000"},{"key":"e_1_2_8_26_2","doi-asserted-by":"publisher","DOI":"10.1002\/ett.1371"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.21508","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.21508","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.21508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,10]],"date-time":"2023-10-10T06:13:43Z","timestamp":1696918423000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.21508"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,28]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1002\/net.21508"],"URL":"https:\/\/doi.org\/10.1002\/net.21508","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,28]]}}}