Friday, 10:30 - 10:55 h, Room: H 3002

 

Michal Pioro
On a survivable network design problem with one or two failing links and elementary path-flows

Coauthors: Dritan Nace, Artur Tomaszewski, Mateusz Zotkiewicz

 

Abstract:
A well known problem in survivable network design consists in minimizing the cost of links under a single link failure scenario (any link can fail but only one at a time) assuming flow restoration. The problem, denoted by FR, assumes bifurcated primary and restoration flows, and stub release (the capacity of links released by failing flows is used for restoration). FR can be expressed as a linear program but only in a non-compact formulation with NP-hard separation. Because of that, FR is regarded as NP-hard itself although this has not been proved.
The paper considers a version of FR when only one predefined link or only two predefined links can fail. We assume that the primary paths cannot contain loops - an assumption commonly neglected. We show that the case with one failing link is polynomial while the case with two failing links is NP-hard. This is a new result that sheds light on FR also for the single link failure scenario. As a byproduct of the one-failing link case, we obtain an example of a non-compact LP formulation with NP-hard separation which actually describes a polynomial problem. Such an example has not been commonly known to the network design community before.

 

Talk 1 of the invited session Fri.1.H 3002
"Optimization modeling of communication networks" [...]
Cluster 23
"Telecommunications & networks" [...]

 

  signature loans . You can buy Levitra Super Force profitably on our web-site; we offer the medications only of the highest quality and at reasonable prices.