Invited Session Wed.2.H 3002

Wednesday, 13:15 - 14:45 h, Room: H 3002

Cluster 23: Telecommunications & networks [...]

Length bounded trees


Chair: Markus Leitner



Wednesday, 13:15 - 13:40 h, Room: H 3002, Talk 1

Ivana Ljubic
Layered graph models for hop constrained trees with multiple roots

Coauthors: Luis Gouveia, Markus Leitner


We consider a network design problem that generalizes the hop constrained Steiner tree problem as follows:
Given an edge-weighted undirected graph whose nodes are partitioned into a set of root nodes, a set of terminals and a set of Steiner nodes, find a minimum-weight subtree that spans all the roots and terminals so that the number of hops between each relevant node and an arbitrary root does not exceed a given hop limit. The set of relevant nodes may be equal to the set of terminals, or to the union of terminals and root nodes.
We first introduce a natural mixed integer programming formulation using edge and node decision variables based on jump cuts. We then propose models utilizing one layered graph for each root node. Possibilities to relate solutions on the layered graphs and additional strengthening inequalities are discussed. Furthermore, theoretical comparisons between these models and previously proposed flow-based and path-based models are given.
To solve the problem to optimality, we implement branch-and-cut algorithms for the layered graph formulations.
These show clear computational advantages over previously existing approaches.



Wednesday, 13:45 - 14:10 h, Room: H 3002, Talk 2

Markus Leitner
New models for the diameter constrained steiner tree problem

Coauthors: Luis Gouveia, Ivana Ljubic


We consider the diameter constrained minimum Steiner tree problem on a graph (DCSTP).
Given an edge-weighted undirected graph whose nodes are partitioned into a set of terminal and Steiner nodes, the objective is to find a minimum-weight subtree that spans all terminal nodes such that the number of hops between any two terminal nodes does not exceed a given diameter D.
In this work, we introduce integer linear programming models for the DCSTP based on the concept of triangles, i.e. diameter constrained Steiner trees induced by terminal subsets of size three.
Starting from a generic formulation including abstract triangle constraints, we discuss various possibilities of realizing them including multi-commodity, common, and uncommon flows. Furthermore, we propose a model utilizing an exponential set of variables, each corresponding to one feasible triangle. We show, how the linear programming relaxation of this model can be solved by column generation or Lagrangian relaxation. Finally, we study the possibility of further strengthening these models using reformulation by intersection.



Wednesday, 14:15 - 14:40 h, Room: H 3002, Talk 3

Andreas Bley
Capacitated facility location with length bounded trees

Coauthors: Jannik Matuschke, Benjamin Müller


We consider a generalization of the Capacitated Facility Location problem, where clients may connect to open facilities via trees shared by multiple clients. The total demand of clients served by a single tree must not exceed a given tree capacity. Furthermore, the length of the path between a client and its facility within the corresponding tree must not exceed a given length bound. The task is to choose open facilities and shared service trees in such a way that the sum of the facility costs and the tree costs is minimal. This problem arises, for example, in the planning of optical access networks in telecommunications, where multiple clients may share a fiber tree if both fiber capacity and signal attenuation on the resulting connection paths permit.
We show that the problem is as hard as Set Cover in general and approximable with a constant factor for metric edge lengths that individually do not exceed the length bound. For the latter case, we present a general approximation algorithm and discuss several modifications of this algorithm that yield better approximation ratios or additional solution properties in special cases.


  The best way to go for you to know the credible Payday Loans Michigan providers. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra influence on blood clots.