On the complexity of resilient network design
(2010) In Networks 55(2). p.108-118- Abstract
- In this article we prove NP-hardness of two well-known
optimization problems related to the design of multicommodity
flow networks with two different methods
for providing network resiliency against failures: path
diversity and flow restoration. Path diversity is a static
mechanism that consists of using, for each demand, a
number of paths and oversizing the flows assigned to
these paths so that for any failure the total surviving flow
is not less than the volume of the demand. By contrast,
flow restoration is a dynamic mechanism that consists
of reassigning the failed flows to backup paths when a
failure occurs. Both mechanisms are of... (More) - In this article we prove NP-hardness of two well-known
optimization problems related to the design of multicommodity
flow networks with two different methods
for providing network resiliency against failures: path
diversity and flow restoration. Path diversity is a static
mechanism that consists of using, for each demand, a
number of paths and oversizing the flows assigned to
these paths so that for any failure the total surviving flow
is not less than the volume of the demand. By contrast,
flow restoration is a dynamic mechanism that consists
of reassigning the failed flows to backup paths when a
failure occurs. Both mechanisms are of practical interest
because although flow restoration is in general superior
to path diversity in terms of the required amount of
resource capacity, it might be too complicated to implement.
By providing an appropriate reduction from the
fractional graph coloring problem, we show that both
problems are NP-hard in the general case of failure
scenarios that admit simultaneous failures of multiple
links. Finally, we discuss how to efficiently solve the two
problems using path generation techniques. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/1363112
- author
- Tomaszewski, A ; Pioro, Michal LU and Zotkiewicz, M
- organization
- publishing date
- 2010
- type
- Contribution to journal
- publication status
- published
- subject
- in
- Networks
- volume
- 55
- issue
- 2
- pages
- 108 - 118
- publisher
- John Wiley & Sons Inc.
- external identifiers
-
- wos:000274946600005
- scopus:77049101234
- ISSN
- 1097-0037
- DOI
- 10.1002/net.20321
- language
- English
- LU publication?
- yes
- id
- c735dcf2-ed1a-4054-afb8-7e20ca8795a0 (old id 1363112)
- date added to LUP
- 2016-04-04 09:39:07
- date last changed
- 2022-01-29 18:54:11
@article{c735dcf2-ed1a-4054-afb8-7e20ca8795a0,
abstract = {{In this article we prove NP-hardness of two well-known<br/><br>
optimization problems related to the design of multicommodity<br/><br>
flow networks with two different methods<br/><br>
for providing network resiliency against failures: path<br/><br>
diversity and flow restoration. Path diversity is a static<br/><br>
mechanism that consists of using, for each demand, a<br/><br>
number of paths and oversizing the flows assigned to<br/><br>
these paths so that for any failure the total surviving flow<br/><br>
is not less than the volume of the demand. By contrast,<br/><br>
flow restoration is a dynamic mechanism that consists<br/><br>
of reassigning the failed flows to backup paths when a<br/><br>
failure occurs. Both mechanisms are of practical interest<br/><br>
because although flow restoration is in general superior<br/><br>
to path diversity in terms of the required amount of<br/><br>
resource capacity, it might be too complicated to implement.<br/><br>
By providing an appropriate reduction from the<br/><br>
fractional graph coloring problem, we show that both<br/><br>
problems are NP-hard in the general case of failure<br/><br>
scenarios that admit simultaneous failures of multiple<br/><br>
links. Finally, we discuss how to efficiently solve the two<br/><br>
problems using path generation techniques.}},
author = {{Tomaszewski, A and Pioro, Michal and Zotkiewicz, M}},
issn = {{1097-0037}},
language = {{eng}},
number = {{2}},
pages = {{108--118}},
publisher = {{John Wiley & Sons Inc.}},
series = {{Networks}},
title = {{On the complexity of resilient network design}},
url = {{http://dx.doi.org/10.1002/net.20321}},
doi = {{10.1002/net.20321}},
volume = {{55}},
year = {{2010}},
}