An 11/6-approximation algorithm for the network steiner problem

An instance of the Network Steiner Problem consists of an undirected graph with edge lengths and a subset of vertices; the goal is to find a minimum cost Steiner tree of the given subset (i.e., minimum cost subset of edges which spans it). An 11/6-approximation algorithm for this problem is given. The approximate Steiner tree can be computed in the time0(¦V¦ ¦E¦ + ¦S¦⁴), whereV is the vertex set,E is the edge set of the graph, andS is the given subset of vertices.     

A series of approximation algorithms for the acyclic directed steiner tree problem

Given an acyclic directed network, a subsetS of nodes (terminals), and a rootr, theacyclic directed Steiner tree problem requires a minimum-cost subnetwork which contains paths fromr to each terminal. It is known that unlessNP⊆DTIME[n ^polylogn ] no polynomial-time algorithm can guarantee better than (lnk)/4-approximation, wherek is the number of terminals. In this paper we give anO(k ^ε)-approximation algorithm for any ε>0. This result improves the previously knownk-approximation. This research was supported in part by Volkswagen-Stiftung and Packard Foundation.     

A novel neural network method for shortest path tree computation

Shortest path tree (SPT) computation is a critical issue in many real world problems, such as routing in networks. It is also a constrained optimization problem, which has been studied by many authors in recent years. Typically, it is solved by heuristic algorithms, such as the famous Dijkstra's algorithm, which can quickly provide a good solution in most instances. However, with the scale of problem increasing, these methods are inefficient and may consume a considerable amount of CPU time. Neural networks, which are massively parallel models, can solve this question easily. This paper presents an efficient modified continued pulse coupled neural network (MCPCNN) model for SPT computation in a large scale instance. The proposed model is topologically organized with only local lateral connections among neurons. The start neuron fires first, and then the firing event spreads out through the lateral connections among the neurons, like the propagation of a wave. Each neuron records its parent, that is, the neighbor which caused it to fire. It proves that the generated wave in the network spreads outward with travel times proportional to the connection weight between neurons. Thus, the generated path is always the global optimal shortest path from the source to all destinations. The proposed model is also applied to generate SPTs for a real given graph step by step. The effectiveness and efficiency of the proposed approach is demonstrated through simulation and comparison studies.     

Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors

We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n ² log n) toO(n log² n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.     

Hopfield Neural Networks for Parametric Identification of Dynamical Systems

In this work, a novel method, based upon Hopfield neural networks, is proposed for parameter estimation, in the context of system identification. The equation of the neural estimator stems from the applicability of Hopfield networks to optimization problems, but the weights and the biases of the resulting network are time-varying, since the target function also varies with time. Hence the stability of the method cannot be taken for granted. In order to compare the novel technique and the classical gradient method, simulations have been carried out for a linearly parameterized system, and results show that the Hopfield network is more efficient than the gradient estimator, obtaining lower error and less oscillations. Thus the neural method is validated as an on-line estimator of the time-varying parameters appearing in the model of a nonlinear physical system.     

Improved Global Robust Stability for Interval-Delayed Hopfield Neural Networks

A modified form of a recent criterion for the global robust stability of interval-delayed Hopfield neural networks is presented. The effectiveness of the modified criterion is demonstrated with the help of an example.     

On the terminal Steiner tree problem

We investigate a practical variant of the well-known graph Steiner tree problem. In this variant, every target vertex is required to be a leaf vertex in the solution Steiner tree. We present hardness results for this variant as well as a polynomial time approximation algorithm with performance ratio ρ+2, where ρ is the best-known approximation ratio for the graph Steiner tree problem.     

Neural network modelling and control strategies for a pH process

The control of a pH process using neural networks is examined. The neural network as a universal approximator is used to good effect in this nonlinear problem, as is shown in the simulation results. In the modelling task, the dynamics of the process was carefully examined to determine a suitable structure for the net. In particular, a multilayer net consisting of two single hidden layers was constructed to reflect the Wiener model of the pH process. This led to much simpler training compared to similar modelling attempts by other researchers. For the control task, two schemes were simulated. In one approach, a net was used to deal with the static nonlinearity to achieve control over a wide working range. The dynamic controller used was the PID, with its parameters tuned on a relay auto-tuner. This control design was compared with the strong acid equivalent method. In the second approach, a direct model reference adaptive neural network control scheme was proposed. The training procedure uses the more efficient least squares algorithm developed by Loh and Fong.     

A note on the terminal Steiner tree problem

In 2002, Lin and Xue [Inform. Process. Lett. 84 (2002) 103-107] introduced a variant of the graph Steiner tree problem, in which each terminal vertex is required to be a leaf in the solution Steiner tree. They presented a ρ+2 approximation algorithm, where ρ is the approximation ratio of the best known efficient algorithm for the regular graph Steiner tree problem. In this note, we derive a simplified algorithm with an improved approximation ratio of 2ρ (currently ρ≈1.550, see [SODA 2000, 2000, pp. 770-790]).     

基于暂态混沌神经网络的组播路由算法

讨论了高速包交换计算机网络中具有端到端时延的组播路由问题。首先给出了这类问题的网络模型及其数学描述,然后提出了基于暂态混沌神经网络的组播路由算法。实验结果表明,该算法能够快速有效地实现组播路由优化,并且计算性能及解的质量优于基于Hopfield神经网络的路由算法。     

Two probabilistic results on rectilinear steiner trees

In recent years, researchers have proven many theorems of the following form: given points distributed according to a Poisson process with intensity parameterN on the unit square, the length of the shortest spanning tree (rectilinear Steiner tree, traveling salesman tour, or some other functional) on these points is, with probability one, asymptotic to N for some constant (which is presumably different for different functionals). Though these theorems are well understood, very little is known about the constants . In this paper we prove that the constants in the cases of rectilinear spanning tree and rectilinear Steiner tree do, indeed, differ. This proof is constructive in the sense that we give a polynomial-time heuristic algorithm that produces a Steiner tree of expected length some fraction shorter than a minimum spanning tree. We continue the analysis to prove a second result: the expected value of the minimum number of Steiner points in a shortest rectilinear Steiner tree grows linearly withN.Research supported in part by NSF Grant MCS-8311422. A preliminary version of this paper appeared in theProceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986.     

On approximation algorithms for the terminal Steiner tree problem

The terminal Steiner tree problem is a special version of the Steiner tree problem, where a Steiner minimum tree has to be found in which all terminals are leaves. We prove that no polynomial time approximation algorithm for the terminal Steiner tree problem can achieve an approximation ratio less than (1−o(1))lnn unless NP has slightly superpolynomial time algorithms. Moreover, we present a polynomial time approximation algorithm for the metric version of this problem with a performance ratio of 2ρ, where ρ denotes the best known approximation ratio for the Steiner tree problem. This improves the previously best known approximation ratio for the metric terminal Steiner tree problem of ρ+2.     

一种非线性优化的神经网络

本文提出了用人工神经网络求解具有约束条件的非线性优化问题的具体方法，分析了神经网络能量函数的构成形式，并在常规的Ｈｏｐｆｉｅｌｄ网络模型的基础上构造了一个非全局连接的神经网络动力学模型。这种修改的Ｈｏｐｆｉｅｌｄ网络克服了常规的Ｈｏｐｆｉｅｌｄ网络在求解非线性优化问题时权值不好映射的困难，具有结构清晰，易于软件模拟和硬件实现的优点。     

The repeater tree construction problem

A tree-like substructure on a computer chip whose task is to carry a signal from a source circuit to possibly many sink circuits and which consists only of wires and so-called repeater circuits is called a repeater tree. We present a mathematical formulation of the optimization problems related to the construction of such repeater trees. Furthermore, we prove theoretical properties of a simple iterative procedure for these problems which was successfully applied in practice.     

离散Hopfield神经网络的稳定性分析

主要研究非对称离散Hopfield神经网络并行演化方式的动力学行为,同时给出了网络的一些新的稳定性条件,所获结果不仅推广了一些已有的结论,而且为该网络的应用提供了一定的理论基础。     

Effects of node processing time on optimal load balancing in tree hierarchy network configurations

In this paper, optimal static load balancing in a tree hierarchy network that consists of a set of heterogeneous host computers is considered. It is formulated as a nonlinear optimization problem. By parametric analysis, we study the effects of the node processing time on the optimal link flow rate (i.e. the rate at which a node forwards jobs to other nodes for remote processing), the optimal node load (i.e. the rate at which jobs are processed at a node), and the optimal mean response time. We show that the entire network can be divided into several independent sub-tree networks with respect to the link flow rates and node loads. We find that the processing time of a node affects only the link flow rates and the loads of nodes which are in the same sub-tree network. Generally, an increase in the processing time of an arbitrary node causes an increase in the link flow rates of its ancestor nodes and itself, but causes a decrease in the link flow rates of its descendant nodes and its collateral nodes in the same sub-tree network. It also causes a decrease in the load of the node itself, but causes an increase in the loads of other nodes in the same sub-tree network. Furthermore, it causes an increase in the mean response time. By conducting numerical experiments, we find that the node processing time possesses a large influence on the system performance measures. Knowledge of the effects of node processing time is useful in designing networks or making a parametric adjustment to improve the system performance.     

Neural computation for collision-free path planning

Automatic path planning plays an essential role in planning of assembly or disassembly of products, motions of robot manipulators handling part, and material transfer by mobile robots in an intelligent and flexible manufacturing environment. The conventional methodologies based on geometric reasoning suffer not only from the algorithmic difficulty but also from the excessive time complexity in dealing with 3-D path planning. This paper presents a massively parallel, connectionist algorithm for collision-free path planning. The path planning algorithm is based on representing a path as a series ofvia points or beads connected by elastic strings which are subject to displacement due to a potential field or a collision penalty function generated by polyhedral obstacles. Mathematically, this is equivalent to optimizing a cost function, defined in terms of the total path length and the collision penalty function, by moving thevia points simultaneously but individually in the direction that minimizes the cost function. Massive parallelism comes mainly from: (1) the connectionist model representation of obstacles and (2) the parallel computation of individualvia-point motions with only local information. The algorithm has power to deal effectively with path planning of three-dimensional objects with translational and rotational motions. Finally, the algorithm incorporates simulated annealing to solve a local minimum problem. Simulation results are shown.     

On greedy heuristics for steiner minimum trees

We disprove a conjecture of Shor and Smith on a greedy heuristic for the Steiner minimum tree by showing that the length ratio between the Steiner minimum tree and the greedy tree constructed by their method for the same set of points can be arbitrarily close to3/2. We also propose a new conjecture.Supported in part by the National Science Foundation under Grant CCR-9208913.     

Two new criteria for finding Steiner hulls in Steiner tree problems

The Steiner tree problem considered in this paper is that of finding a network of minimum length connecting a given setK of terminals in a regionR of the Euclidean plane. ASteiner hull forK inR is any subregion ofR known to contain a Steiner tree forK inR. Two new criteria are given for finding Steiner hulls—one for the Steiner tree problem on plane graphs and one for the rectilinear Steiner tree problem—which strengthen known polynomial-time methods of finding Steiner hulls.This research was supported by the Air Force Office of Scientific Research under Grant AFOSR-84-0140. Reproduction in whole or part is permitted for any purpose of the United States Government.     

一类非对称Hopfield神经网络稳定性的敏感性研究

对一类非对称Hopfield神经网络在联接矩阵为非对称的前提下对矩阵特征值所在范围作了更精细的刻画;在有电容（C）扰动下利用矩阵特征理论给出了网络渐近稳定性的条件。