TY - GEN A1 - Bley, Andreas A1 - Grötschel, Martin A1 - Wessäly, Roland T1 - Design of Broadband Virtual Private Networks: Model and Heuristics for the B–WiN N2 - We investigate the problem of designing survivable broadband virtual private networks that employ the Open Shortest Path First (OSPF) routing protocol to route the packages. The capacities available for the links of the network are a minimal capacity plus multiples of a unit capacity. Given the directed communication demands between all pairs of nodes, we wish to select the capacities in a such way, that even in case of a single node or a single link failure a specified percentage of each demand can be satisfied and the costs for these capacities are minimal. We present a mixed--integer linear programming formulation of this problem and several heuristics for its solution. Furthermore, we report on computational results with real-world data. T3 - ZIB-Report - SC-98-13 KW - Telecommunication Network Design KW - Survivable Networks KW - Network Capacity Planning KW - OSPF Routing KW - Shortest Path Routing KW - Heuristics Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3565 ER - TY - GEN A1 - Bley, Andreas T1 - Inapproximability Results for the Inverse Shortest Paths Problem with Integer Length and Unique Shortest Paths N2 - We study the complexity of two Inverse Shortest Paths (ISP) problems with integer arc lengths and the requirement for uniquely determined shortest paths. Given a collection of paths in a directed graph, the task is to find positive integer arc lengths such that the given paths are uniquely determined shortest paths between their respective terminals. The first problem seeks for arc lengths that minimize the length of the longest of the prescribed paths. In the second problem, the length of the longest arc is to be minimized. We show that it is $np-hard$ to approximate the minimal longest path length within a factor less than $8/7$ or the minimal longest arc length within a factor less than $9/8$. This answers the (previously) open question whether these problems are $np-hard$ or not. We also present a simple algorithm that achieves an $\mathcal{O}(|V|)$-approximation guarantee for both variants. Both ISP problems arise in the planning of telecommunication networks with shortest path routing protocols. Our results imply that it is $\mathcal{NP}$-hard to decide whether a given path set can be realized with a real shortest path routing protocol such as OSPF, IS-IS, or RIP. T3 - ZIB-Report - 05-04 KW - Inverse Shortest Paths KW - Computational Complexity KW - Approximation KW - Shortest Path Routing Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8388 ER -