Uncertainty in Discrete Optimization: Connectivity and Covering

  • Dealing with uncertain structures or data has lately been getting much attention in discrete optimization. This thesis addresses two different areas in discrete optimization: Connectivity and covering. When discussing uncertain structures in networks it is often of interest to determine how many vertices or edges may fail in order for the network to stay connected. Connectivity is a broad, well studied topic in graph theory. One of the most important results in this area is Menger's Theorem which states that the minimum number of vertices needed to separate two non-adjacent vertices equals the maximum number of internally vertex-disjoint paths between these vertices. Here, we discuss mixed forms of connectivity in which both vertices and edges are removed from a graph at the same time. The Beineke Harary Conjecture states that for any two distinct vertices that can be separated with k vertices and l edges but not with k-1 vertices and l edges or k vertices and l-1 edges there exist k+l edge-disjoint paths between them of which k+1 are internally vertex-disjoint. In contrast to Menger's Theorem, the existence of the paths is not sufficient for the connectivity statement to hold. Our main contribution is the proof of the Beineke Harary Conjecture for the case that l equals 2. We also consider different problems from the area of facility location and covering. We regard problems in which we are given sets of locations and regions, where each region has an assigned number of clients. We are now looking for an allocation of suppliers into the locations, such that each client is served by some supplier. The notable difference to other covering problems is that we assume that each supplier may only serve a fixed number of clients which is not part of the input. We discuss the complexity and solution approaches of three such problems which vary in the way the clients are assigned to the suppliers.
Metadaten
Author:Manuel StreicherORCiD
URN:urn:nbn:de:hbz:386-kluedo-65558
DOI:https://doi.org/10.26204/KLUEDO/6555
ISBN:978-3-8439-4683-4
Publisher:Verlag Dr. Hut
Place of publication:München
Advisor:Sven Oliver Krumke
Document Type:Doctoral Thesis
Language of publication:English
Date of Publication (online):2021/09/02
Date of first Publication:2021/01/28
Publishing Institution:Technische Universität Kaiserslautern
Granting Institution:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2020/12/04
Date of the Publication (Server):2021/09/03
Tag:Connectivity; Cycle Decomposition; Graph Theory; Mixed Connectivity; Multiset Multicover; Robust Optimization
Page Number:IX, 149
Source:https://www.dr.hut-verlag.de/9783843946834.html
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
CCS-Classification (computer science):G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.1 Combinatorics (F.2.2) / Combinatorial algorithms
G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.2 Graph Theory (F.2.2) / Path and circuit problems
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Classification (mathematics):05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C38 Paths and cycles [See also 90B10]
05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C40 Connectivity
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C11 Mixed integer programming
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C17 Robustness in mathematical programming
Licence (German):Zweitveröffentlichung