Combinatorial Algorithms for Some Variants of Inverse Obnoxious Median Location Problem on Tree Networks

This paper concerns with some variants of the inverse obnoxious median location problem on tree networks, where the aim is either to augment or to reduce the edge lengths at the minimum total cost such that a prespecified subset of vertices becomes an obnoxious multi-facility median location with respect to the perturbed edge lengths. For both augmentation and reduction models, under the rectilinear norm and the sum-type Hamming distance, we develop novel combinatorial algorithms with polynomial time complexities. Particularly, if the underlying tree is an extended star graph, then the problems can be solved in linear time.     

网络上的选址博弈模型

研究了具有竞争关系的两公司在由客户组成的网络上先后进行选址的情形,将这种情形建模成一个S tackelberg博弈.由于商店选址之后,客户的行为是自发的,在这种情况下,客户之间往往会有合作,以降低车辆路径费用.提出利用车辆路径合作博弈来模拟客户的行为,从而确定各商店的客户集,并将这种方法与直接利用客户到商店的距离来确定商店的客户集的方法进行了统计意义上的比较.     

The Tree of Hubs Location Problem

This paper presents the Tree of Hubs Location Problem. It is a network hub location problem with single assignment where a fixed number of hubs have to be located, with the particularity that it is required that the hubs are connected by means of a tree. The problem combines several aspects of location, network design and routing problems. Potential applications appear in telecommunications and transportation systems, when set-up costs for links between hubs are so high that full interconnection between hub nodes is prohibitive. We propose an integer programming formulation for the problem. Furthermore, we present some families of valid inequalities that reinforce the formulation and we give an exact separation procedure for them. Finally, we present computational results using the well-known AP and CAB data sets.     

Minmax p-Traveling Salesmen Location Problems on a Tree

Suppose that p traveling salesmen must visit together all points of a tree, and the objective is to minimize the maximum of the lengths of their tours. The location–allocation version of the problem (where both optimal home locations of the salesmen and their optimal tours must be found) is known to be NP-hard for any p2. We present exact polynomial algorithms with a linear order of complexity for location versions of the problem (where only optimal home locations must be found, without the corresponding tours) for the cases p=2 and p=3.     

Location Problems Arising in Computer Networks

The planning and organization of computer networks give rise to many location problems. These may be split into those primarily concerned with placement of hardware and those with software. Here a broad overview of location and hardware components is given, together with a brief appraisal of the ‘state of the art’ for various problems.     

Essential Spanning Forests and Electrical Networks on Groups

Let be a Cayley graph of a finitely generated group G. Subgraphs which contain all vertices of , have no cycles, and no finite connected components are called essential spanning forests. The set of all such subgraphs can be endowed with a compact topology, and G acts on by translations. We define a uniform G-invariant probability measure on show that is mixing, and give a sufficient condition for directional tail triviality. For non-cocompact Fuchsian groups we show how can be computed on cylinder sets. We obtain as a corollary, that the tail -algebra is trivial, and that the rate of convergence to mixing is exponential. The transfer-current function (an analogue to the Green function), is computed explicitly for the Modular and Hecke groups.     

基于贝叶斯网络的多态故障树分析方法

针对多态系统故障树分析的难点,通过一个多态雷达系统的实例给出了一种基于贝叶斯网络的多态故障树分析方法.首先根据多态故障树的结构建立贝叶斯网络的拓扑结构,然后根据多态逻辑算子对其进行定量化,进而利用贝叶斯网络分析多态故障树顶事件概率、部件重要度及其它结果.最后通过对实例的分析说明了基于贝叶斯网络的多态故障树分析方法有更强的建模分析能力.     

干线网络的选址问题研究

考虑平面上和三维空间中同时确定多条干线的干线网络选址问题.对于平面上情形,通过最小化每个点到离它最近干线的加权距离之和,给出了一种有限步终止算法和基于k-means聚类分析、加权全最小一乘和重抽样方法的线性类算法;对于空间情形,给出了线性聚类算法.通过计算机仿真说明以上算法可以有效地确定平面和空间中干线网络位置.     

基于加权绝对值距离Steiner最优树的选址问题

提出基于加权绝对值距离Steiner最优树思想的选址模型,给出了该模型的蚂蚁算法实现策略.在此基础上,分析了电子商务环境下企业配送中心选址问题,并用算例验证了该选址方案的可行性.     

基于空间故障树理论的系统故障定位方法研究

为了系统发生不同类型故障后快速定位可能引起该故障的系统元件,通过分析系统结构和元件故障概率分布,以及系统在不同工作环境中发生各类型故障的统计数量,提出基于空间故障树(Space Fault Tree,SFT)理论的系统故障定位方法.该方法使用SFT概念得到系统内部结构及元件的故障概率矩阵P(X_i),分析元件X_i故障对于所在割集S_j及系统T故障的贡献度,结合系统故障次数统计矩阵Γ(m_q),最终得到元件X_(1~I)与故障m_(1~Q)的相关度矩阵.这个矩阵可反映出对于任意系统故障m_q与故障元件X_(1~I)的相关性排序、对应的割集、及保证结论正确的可能性,还可优化系统故障分类.实例研究表明:方法可确定各故障的至因故障元件,并根据可能性进行排序,排序靠前的元件组合正是系统的割集,这从侧面也说明了方法正确性.     

All Stackelberg Location Equilibria in the Hotelling's Duopoly Model on a Tree with Parametric Prices

The sequential Hotelling's duopoly model on a tree was studied by Eiselt (1992), who developed conditions for the existence of location equilibria when location decisions are nodes and prices are parametric. In this paper, this competition model is also analyzed, but considering that locations for the two firms can be any pair of points on the tree, nodes or points in the edges. First, a condition is given under which both the leader and the follower get a positive profit. In this setting, the problem of finding optimal locations for each of them is studied with different and equal prices. In both cases, the set of optimal locations for the follower is generated for any location of the leader as well as the set of optimal locations for the leader. As a consequence the entire set of Stackelberg solutions to this competition model is obtained.     

A Joint DAE/PDE Model for Interconnected Electrical Networks

To model transmission lines effects in integrated circuits, we couple the network equations for the circuits with the telegrapher's equations for the transmission lines. This results in an initial/boundary value problem for a mixed system of Differential-Algebraic Equations (DAEs) and hyperbolic Partial Differential Equations (PDEs). By semidiscretization the system is transformed into differential-algebraic equations in time only. We apply this modeling approach to a CMOS ring oscillator, an oscillatory circuit with transmission lines as coupling units, and discuss the simulation results.     

Neural Networks,Decision Tree Induction and Discriminant Analysis: an Empirical Comparison

This paper presents an empirical comparison of three classification methods: neural networks, decision tree induction and linear discriminant analysis. The comparison is based on seven datasets with different characteristics, four being real, and three artificially created. Analysis of variance was used to detect any significant differences between the performance of the methods. There is also some discussion of the problems involved with using neural networks and, in particular, on overfitting of the training data. A comparison between two methods to prevent overfitting is presented: finding the most appropriate network size, and the use of an independent validation set to determine when to stop training the network.     

Improved Self-Stabilizing Algorithms for L(2, 1)-Labeling Tree Networks

The L(2, 1)-labeling problem for a graph G is a variation of the standard graph coloring problem. Here, we seek to assign a label (color) to each node of G such that nodes a distance of two apart are assigned unique labels and adjacent nodes receive labels which are at least two apart. In a previous paper—presented at the 23rd IASTED International Multi-Conference: Parallel and Distributed Computing and Networks, Innsbruck, Austria—we presented, to the best of our knowledge, the first self-stabilizing algorithm which {Δ +  2}-L(2, 1)-labels rooted trees. That algorithm was shown to require an exponential number of moves to stabilize on a global solution (which is not uncommon in self-stabilizing systems). In this paper, we present two self-stabilizing algorithms which {Δ +  2}-L(2, 1)-label a given rooted tree T in only O(nh) moves (where h is the height and n is the number of nodes in the tree T) under a central scheduler. We also show how the algorithms may be adapted to unrooted trees, dynamic topology changes, and consider the correctness of the protocols under the distributed scheduler model.     

Improving Construction for Connected Dominating Set with Steiner Tree in Wireless Sensor Networks

The connected dominating set plays an important role in ad hoc wireless networking. Many constructions for approximating the minimum connected dominating set have been proposed in the literature. In this paper, we propose a new one with Steiner tree, which produces approximation solution within a factor of 6.8 from optimal. This approximation algorithm can also be implemented distributedly.     

Tree polytope on 2-trees

We give a complete polyhedral characterization of the tree polytope (convex hull of the characteristic vectors of trees in the graph) on 2-trees.     

Facility Location on a Sphere

In this paper, we consider a modification of the Weber problem which consists of locating a new facility on a sphere so that the weighted sum of distances to given demand points is minimized. Two ways of measuring distance are used. One is simply the length of shortest arc on the sphere. The other norm, first suggested by Katz and Cooper, may be used to approximate squared arc distance on a hemisphere and also as a rough approximation for arc distance. Several properties of the problem are established. An iterative heuristic method for solving the problem with shortest arc distances is presented.     

离散设施选址问题研究综述

本文首先回顾了设施选址问题百年发展历史,认为其研究经历了零散研究、系统研究、不确定性研究三个阶段.离散选址问题包括中值问题、覆盖问题、中心问题、多产品问题、动态问题、多目标问题、路径选址问题、网络中心选址问题8个子问题.最后作者讨论了选址问题研究中存在的问题以及今后发展的趋势.     

Group Actions on the Cubic Tree

It is known that every group which acts transitively on the ordered edges of the cubic tree ₃, with finite vertex stabilizer, is isomorphic to one of seven finitely presented subgroups of the full automorphism group of ₃–one of which is the modular group. In this paper a complete answer is given for the question (raised by Djokovi and Miller) as to whether two such subgroups which intersect in the modular group generate their free product with the modular group amalgamated.     

Linear Recurrence Equations on a Tree

We construct an algorithm that tests a system of recurrence equations on a tree for the existence of a nontrivial solution and computes it.