Monday, 15:45 - 16:10 h, Room: MA 004


David Adjiashvili
Fault-tolerant shortest paths - Beyond the uniform failure model


The overwhelming majority of survivable (fault-tolerant) network design models assume a uniform scenario set. Such a scenario set assumes that every subset of the network resources (edges or vertices) of a given cardinality k comprises a scenario. While this approach yields problems with clean combinatorial structure and good algorithms, it often fails to capture the true nature of robustness coming from applications.
One natural refinement of the uniform model is obtained by partitioning the set of resources into faulty and secure resources. The scenario set contains every subset of at most k faulty resources. This work studies the Fault-Tolerant Path (FTP) problem, the counterpart of the Shortest Path problem in this failure model. We present complexity results alongside exact and approximation algorithms for FTP. We emphasize the vast increase in the complexity of the problem with respect to its uniform analogue, the Edge-Disjoint Paths problem.


Talk 2 of the invited session Mon.3.MA 004
"Robust network optimization" [...]
Cluster 20
"Robust optimization" [...]


  Florida Payday Loans can help you in trying times, but be sure to know the laws necessary for your loan application. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.