 |
|
||||||||||
Combinatorial Methods for Analyzing Network Security and Reliability
IFOR Events
Seminar:
'Optimization & Applications' (see information & program)
Feb 18 - May 27, 2013
| Author | Rico Zenklusen |
| Abstract |
The main focus in most classical network optimization problems lies on performability. In these problems one usually does not consider the possibility that arcs or vertices may be removed from the given network due to failures or other reasons. However, many systems with an underlying network structure are not perfectly reliable and it is often of high interest to consider network models in settings where arcs and vertices may be removed. Unfortunately, relatively little is known about classical network optimization problems in a failure-prone setting. This thesis deals with classical combinatorial optimization problems on networks in settings where arcs and vertices may be subject to removal. It contains results on four topics to be presented next. In all problems we consider, the arcs and vertices that are removed, are all removed simultaneously. The first problem we consider, is the problem of estimating s-t reliabilities in acyclic digraphs. As long as the reliability to estimate is not too small, a crude Monte-Carlo approach can be used to obtain a good estimate with high probability. However, this method needs a tremendous amount of time to deliver good estimates for very small reliabilities. Small reliabilities often have to be estimated in models where one is interested in rare events with a high impact. We suggest a method allowing to estimate very small s-t reliabilities in large acyclic digraphs and present structural conditions on the input network under which the proposed algorithm is an FPRAS. The second problem that will be discussed is known as network flow interdiction and can be described as follows. In a given flow network one has to remove a subset of the arcs constrained to some budget such that the value of a maximum flow in the resulting network is minimized. Although this problem is known to be NP-hard in general, pseudo-polynomial algorithms are known for some special cases of planar instances. We present new approaches that allow to solve in pseudo-polynomial time a wider class of planar instances than previously possible. In particular, we present a method for incorporating the possibility of vertex removals and vertex capacities. Furthermore, an algorithm is presented that can solve a particular type of interdiction problem on networks with multiple sources and sinks. We also show a technique for converting a large class of pseudo-polynomial network flow interdiction algorithms into FPAS's. In the third part of the thesis we introduce the matching interdiction problem which is basically a natural extension of other interdiction problems to matchings. The task is to choose in a given undirected network a subset of edges with respect to some budget such that the weight of a maximum matching in the resulting network is minimized. Hardness results for different types of graph classes are presented. For graphs with bounded treewidth we introduce a pseudo-polynomial algorithm and an FPAS. In the fourth part of this thesis we present a proof for a conjecture raised by Goemans and Vondrák about a bound on the number of edges contained in the union of all minimum spanning trees of fixed sized subgraphs. We show that the proven bound can be seen as a generalization of Mader's theorem which bounds the number of edges in any edge-minimal k-connected graph. |
| Download |
Wichtiger Hinweis:
Diese Website wird in älteren Versionen von Netscape ohne
graphische Elemente dargestellt. Die Funktionalität der
Website ist aber trotzdem gewährleistet. Wenn Sie diese
Website regelmässig benutzen, empfehlen wir Ihnen, auf
Ihrem Computer einen aktuellen Browser zu installieren. Weitere
Informationen finden Sie auf
folgender
Seite.
Important Note:
The content in this site is accessible to any browser or
Internet device, however, some graphics will display correctly
only in the newer versions of Netscape. To get the most out of
our site we suggest you upgrade to a newer browser.
More
information
