In the classical geometric Steiner tree problem, we are given a set of points in the plane and our aim is to find the shortest network interconnecting the set of points. An unlimited number of additional vertices, called Steiner points, may be added to shorten the network. In the minimum k -Steiner tree problem, the number of Steiner points is limited to some nonnegative integer k , which creates additional complexity. This paper improves on the current algorithmic approach to solving the Euclidean k -Steiner tree problem. We introduce a novel pruning test and strengthen existing tests to allow more extensive elimination of sub-optimal topologies during the generation phase of the algorithm. We also introduce a new ILP model for the concatenation phase. Finally, we present experimental results that demonstrate the effectiveness of these novel components.

Abstract We consider the problem of adding a minimum length set of edges to a geometric graph so that the resultant graph is resilient against partition from the effect of a single disaster. Disasters are modeled by discs of given maximum radius, and a disaster destroys all edges intersecting its interior. It is assumed that the input and output graphs are planar with a straight-line embedding. We provide a computationally simple characterisation of feasible input instances in terms of the convex hull of the given graph, and present a fast ILP algorithm for generating optimal solutions. We also perform a computational study which shows that our algorithm is able to solve randomly generated instances with hundreds of nodes.

The Euclidean k-Steiner tree problem asks for a minimum-cost network connecting n given points in the plane, allowing at most k additional nodes referred to as Steiner points. In the classical Steiner tree problem in which there is no restriction on the number of nodes, every Steiner point must be of degree 3. The k-Steiner problem differs in that Steiner points of degree 4 may be included in an optimal solution. This simple change leads to a number of complexities when attempting to create a generation algorithm for optimal k-Steiner trees, which has proven to be a powerful component of the flagship algorithm, namely GeoSteiner, for solving the classical Steiner tree problem. In the present paper we firstly extend the basic framework of GeoSteiner's generation algorithm to include degree-4 Steiner points. We then introduce a number of novel results restricting the structural and geometric properties of optimal k-Steiner trees, and then show how these properties may be used as topological pruning methods underpinning our generation algorithm. Finally, we present experimental data to show the effectiveness of our pruning methods in reducing the number of sub-optimal solution topologies.

Abstract We introduce a formal framework for the study of augmenting networks in the plane for disaster‐resilience, where a disaster is modeled by a straight‐line segment. We generalize various graph structures from classical 2‐edge‐connectivity, including minimal cuts and blocks. The key concept that we introduce is that of an ‐leaf, which builds on the fundamental “leaf‐block” concept from classical augmentation. We present a number of algorithms for constructing the above‐mentioned graph structures, including a sweep‐line algorithm that finds all edge‐cuts that can be destroyed by a single disaster. We also present an algorithm which optimally adds a single edge between a pair of ‐leaves or blocks while avoiding certain disaster regions. Finally, we present a number of heuristic schemes for solving the disaster‐resilient network augmentation problem and perform extensive experiments to demonstrate the power of the ‐leaf concept within heuristic design.

Abstract We present methods for simplifying the geometry of polygonal obstacles as a preprocessing step to solving obstacle‐avoiding Steiner network problems in the plane. The methods reduce the total number of vertices and edges that need to be considered for the given obstacles, and their use is expected to significantly improve the efficiency of exact algorithms for solving a range of practical Steiner network problems in obstacle environments. Included are methods forextendingobstacles (via a newpaddingmethod and abackfillingprocedure from the literature), and various methods for simplifying obstacles, including new methods calledboundingandeliminating. We show that these methods reduce the total number of obstacle vertices and edges by performing experiments on obstacles with up to 100 vertices in the presence of up to 100 terminals. The experiments utilize a modified version of a known algorithm for quickly generating large numbers of “random” polygons with hundreds of vertices. Corresponding datasets and implementations have been made available on GitHub.

Abstract For a given set X of points in the plane, we consider the problem of constructing a 2‐vertex‐connected network spanning X and at most k additional Steiner points such that the length of the longest edge (the so‐called bottleneck) of the network is minimized. When one introduces a constraint on the network specifying that all Steiner points must be of degree 2 the problem remains NP‐complete but becomes fixed parameter tractable with respect to k. We prove this by presenting an algorithm which solves the degree‐2 bounded problem optimally in a time of O(n4k62k), where n = |X|. We also present a simple 3‐approximation algorithm for the degree‐2 bounded problem and show that the bottleneck length of an optimal solution to the degree‐2 bounded problem is at most twice the bottleneck length when degree is not bounded.

When using reinforcement learning (RL) algorithms it is common, given a large state space, to introduce some form of approximation architecture for the value function (VF). The exact form of this architecture can have a significant effect on an agent's performance, however, and determining a suitable approximation architecture can often be a highly complex task. Consequently there is currently interest among researchers in the potential for allowing RL algorithms to adaptively generate (i.e. to learn) approximation architectures. One relatively unexplored method of adapting approximation architectures involves using feedback regarding the frequency with which an agent has visited certain states to guide which areas of the state space to approximate with greater detail. In this article we will: (a) informally discuss the potential advantages offered by such methods; (b) introduce a new algorithm based on such methods which adapts a state aggregation approximation architecture on-line and is designed for use in conjunction with SARSA; (c) provide theoretical results, in a policy evaluation setting, regarding this particular algorithm's complexity, convergence properties and potential to reduce VF error; and finally (d) test experimentally the extent to which this algorithm can improve performance given a number of different test problems. Taken together our results suggest that our algorithm (and potentially such methods more generally) can provide a versatile and computationally lightweight means of significantly boosting RL performance given suitable conditions which are commonly encountered in practice.

Abstract We present a new exact algorithm for computing minimum 2‐edge‐connected Steiner networks in the Euclidean plane. The algorithm is based on the GeoSteiner framework for computing minimum Steiner trees in the plane. Several new geometric and topological properties of minimum 2‐edge‐connected Steiner networks are developed and incorporated into the new algorithm. Comprehensive experimental results are presented to document the performance of the algorithm which can reliably compute exact solutions to randomly generated instances with up to 50 terminals—doubling the range of existing exact algorithms. Finally, we discuss the appearance of Hamiltonian cycles as solutions to the minimum 2‐edge‐connected Steiner network problem.

Given a graph G with edge lengths, the minimum bottleneck spanning tree (MBST) problem is to find a spanning tree where the length of the longest edge in tree is minimum. It is a well‐known fact that every minimum spanning tree (MST) is a minimum bottleneck spanning tree. In this article, we introduce the δ‐MBST problem, which is the problem of finding an MBST such that every vertex in the tree has degree at most δ. We show that optimal solutions to the similarly defined δ‐MST problem are not necessarily optimal solutions to the δ‐MBST, and we establish that the δ‐MBST problem is NP‐complete for any . We show that when edge lengths of the graph are Euclidean distances between points in the plane, the problem is NP‐hard for δ = 2 and 3, and tractable for . We give a dual approximation scheme for the general graph version of the problem which is the best possible with respect to feasibility. For the Euclidean version, we give a ‐factor approximation algorithm for the 4‐MBST. We also give a 2‐factor algorithm for the Euclidean 3‐MBST and a 3‐factor approximation algorithm for the general Euclidean δ‐MBST, both of which can be generalized to metric spaces. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 68(4), 302–314 2016

We introduce a flow‐dependent version of the quadratic Steiner tree problem in the plane. An instance of the problem on a set of embedded sources and a sink asks for a directed tree T spanning of these nodes and a bounded number of Steiner points, such that is a minimum, where f(e) is the flow on edge e. The edges are uncapacitated and the flows are determined additively, that is, the flow on an edge leaving a node u will be the sum of the flows on all edges entering u. Our motivation for studying this problem is its utility as a model for relay augmentation of wireless sensor networks. In these scenarios, one seeks to optimize power consumption—which is predominantly due to communication and, in free space, is proportional to the square of transmission distance—in the network by introducing additional relays. We prove several geometric and combinatorial results on the structure of optimal and locally optimal solution‐trees (under various strategies for bounding the number of Steiner points) and describe a geometric linear‐time algorithm for constructing such trees with known topologies. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(1), 18–28 2014

Abstract We investigate the problem of designing a minimum‐cost flow network interconnecting n sources and a single sink, each with known locations in a normed space and with associated flow demands. The network may contain any finite number of additional unprescribed nodes from the space; these are known as the Steiner points. For concave increasing cost functions, a minimum‐cost network of this sort has a tree topology, and hence can be called a Minimum Gilbert Arborescence (MGA). We characterize the local topological structure of Steiner points in MGAs, showing, in particular, that for a wide range of metrics, and for some typical real‐world cost functions, the degree of each Steiner point is 3. © 2012 Wiley Periodicals, Inc. NETWORKS, 2013

Abstract Given a set of points, we define a minimum Steiner point tree to be a tree interconnecting these points and possibly some additional points such that the length of every edge is at most 1 and the number of additional points is minimized. We propose using Steiner minimal trees to approximate minimum Steiner point trees. It is shown that in arbitrary metric spaces this gives a performance difference of at most 2n‐ 4, wherenis the number of terminals. We show that this difference is best possible in the Euclidean plane, but not in Minkowski planes with parallelogram unit balls. We also introduce a new canonical form for minimum Steiner point trees in the Euclidean plane; this demonstrates that minimum Steiner point trees are shortest total length trees with a certain discrete‐edge‐length condition. © 2010 Wiley Periodicals, Inc. NETWORKS, 2010