A recursive partitioning algorithm for inverting tridiagonal matrices

Motivated by the recursive partitioning algorithm of Evans [2], we present a new algorithm for inverting tridiagonal matrices. Our derivation of the algorithm is different but elementary. The present algorithm has potential for its vector and parallel implementation.     

A fast and reliable multi-sender algorithm for peer-to-peer networks

Due to special constraints in peer-to-peer (P2P) networks (such as bandwidth limitation) and because of their highly dynamic characteristics, a single node cannot provide a reliable multimedia stream to the receivers. Several multi-sender algorithms are proposed to reliably deliver a media stream to the receiver through the intrinsically unreliable P2P networks. Based on upload bandwidths and availability of peers as well as the bandwidths of the links connecting the senders and the receiver, PROMISE selects a set of active senders to maximize the expected bit-rate delivered to the receiver. By careful investigation of PROMISE, in this paper, we present why and how it deviates from finding the optimal solution. The proposed algorithm, we call IPROMISE, consistently provides a higher media quality to the receiver, with a computational complexity similar to PROMISE. We also introduce FastIPROMISE which provides the same quality as IPROMISE but requires much less computations. That is achieved by shrinking the search space.     

一种无线传感器网络可靠拓扑的生成算法

在无线传感器网络（ WSNs）的应用中,网络中的节点需要将采集到的数据信息传送到汇聚节点,其信息传输的可靠性是十分重要的。然而,由于无线通信信道容易受到干扰和噪音的影响,极限情况时甚至可能造成数据传输失败,这对无线传感器网络的正常工作提出了极大挑战。针对上述问题,提出一种可靠拓扑的生成算法,通过该算法设计了一组可靠的路由拓扑,并通过仿真验证了其可靠性。     

An analysis of an approximation algorithm for queueing networks

Queueing network models have proved to be useful aids in computer system performance prediction. Numerous approximation algorithms have been devised to allow queueing networks to be analyzed with a reduced computational expense. In particular, for separable queueing networks several popular iterative approximation algorithms are available.

One disadvantage of these algorithms has been the lack of results concerning their behavior, such as whether or not iteration convergence is guaranteed. This paper presents an analysis of an approximate MVA algorithm proposed by Schweitzer (1979). It is proved that the equations defining the algorithm have a unique solution when there is only a single customer class, and iteration initializations that yield monotonic convergence to this solution are exhibited. It is also proved that the solution is pessimistic relative to the exact queueing network solution.     

On approximating the conditional wait process of general multiserver queueing systems

In view of the extremely difficult task of analyzing G/G/K queueing systems, relatively few general results have been established. Most of the literature dealing with the G/G/K system has been concerned with the heavy traffic situation. Of special note are the bounds given by Kingman[7] on the wait process, the weak convergence theorems established by Iglehart and Whitt[4] and Loulou[8], and the many server approximations due to Newell[9].In this paper a presentation will be made of new formulas constructed to approximate the mean and variance of the conditional wait process. Two key concepts play major roles behind the formulas to be presented. They are: (a) the use of a continuous (diffusion-type) process to approximate the steady-state probabilities of the number in the queue, and (b) the substitution of the original process of interdeparture times by a process of independent variables.In order to assess the quality of the suggested approximation for the mean and variance of the conditional wait process, the approximation will be numerically compared with the results obtained from Kingman's[7] and Kendall's[5] exact formula for the special case of the G/M/K system, and will be tested against point estimate simulations.     

A hybrid algorithm for queueing systems

Abstract In this paper, we propose a hybrid algorithm based on [12] for solving linear systems of equations. The hybrid algorithm combines the evolutionary algorithm and the successive over-relaxation (SOR) method. The evolutionary algorithm allows the relaxation parameter w to be adaptive in the SOR method. We prove the convergence of the hybrid algorithm for strictly diagonal dominant linear systems. We then apply it to solve the steady-state probability distributions of Markovian queueing systems. Numerical examples are given to demonstrate the fast convergence rate of the method.     

Extension of the optimality of the threshold policy inheterogeneous multiserver queueing systems

The authors extend the validity of some results on the optimal control of two-server queueing models with service times of unequal distribution, operating in continuous or discrete time. The distribution of arrivals can be arbitrary subject to some conditions. Both discounted and long-run average costs are considered. Dynamic programming and probabilistic arguments are used to establish the assertion that the optimal policy is of threshold type, i.e. the slower server should be utilized only when the queue length exceeds a certain threshold value     

A novel recursive shared segment protection algorithm in survivable WDM networks

This paper investigates the problem of dynamic survivable routing for shared segment protection in mesh Wavelength-Division-Multiplexing (WDM) optical networks. We propose a heuristic algorithm, named Recursive Shared Segment Protection (RSSP), to introduce a more flexible way to partition the working path into segments and compute the corresponding backup segments. In RSSP, the working segments cannot be determined before the backup segments are found, we adopt a recursive process to compute the backup segments one by one and then choose an optimized way to partition the working path. The calculations of every neighbor working segment and its backup segment are connected with each other. We constrain the hop count for each backup segment to insure the short failure recovery time and control the bandwidth resource utilization. Compared with the Share Path Protection (SPP), RSSP can achieve much shorter failure recovery time with a little sacrifice in bandwidth resource utilization and RSSP can also perform better compromise between the failure recovery time and the bandwidth resource utilization than the Equal-Length Segment Protection (ELSP) algorithm. We evaluate the effectiveness of RSSP and the results are found to be promising.     

Throughput bounding and simple approximation methods for exponential fork/join queueing networks with blocking

Exponential fork/join queueing networks (FJQNs) with finite buffers have been used as a major tool for evaluating the performances of manufacturing systems. In this study, we first suggest the throughput upper and lower bounds. Our upper-bounding method is elaborated on with general network configuration (acyclic configuration), while our lower bounds can be obtained only for networks with more specialized configuration. Next, developed is a simple approximation method for throughputs, which are based on decomposition/aggregation principles and structurally equivalent relations between different configurations.     

一种高效可靠的无线传感器网络定位算法

提出了一种新的基于接收信号强度(RSSI)的无线传感器网络定位算法,将固定锚节点之间的距离和信号强度信息同时作为参考来校正每个固定锚节点的权值,每个节点收集自身到其一跳邻节点的RSSI值,当收集数量达到要求时,对数据进行滤波并求平均值处理.通过理论推导证明该方法可以有效降低RSSI不规则网络的定位误差,进而实现高效定位.仿真结果表明,该定位算法可以降低定位误差,具有高效的可用性,能够应用于实际的无线传感器网络中.     

A generalized method of moments for closed queueing networks

We introduce a new solution technique for closed product-form queueing networks that generalizes the Method of Moments (MoM), a recently proposed exact algorithm that is several orders of magnitude faster and memory efficient than the established Mean Value Analysis (MVA) algorithm. Compared to MVA, MoM recursively computes higher-order moments of queue lengths instead of mean values, an approach that remarkably reduces the computational costs of exact solutions, especially on models with large numbers of jobs.In this paper, we show that the MoM recursion can be generalized to include multiple recursive branches that evaluate models with different numbers of queues, a solution approach inspired by the Convolution algorithm. Combining the approaches of MoM and Convolution simplifies the evaluation of normalizing constants and leads to large computational savings with respect to the recursive structure originally proposed for MoM.     

A recursive construction algorithm for covariance control

This paper proposes an algorithm to compute solutions X to the linear matrix equation and inequality of the type (I-BB⁺)(AX+XA'+W)(I-BB⁺)=0, X>0. This problem arises in the synthesis of covariance controllers; the set of symmetric matrices X assignable as a closed-loop state covariance by a stabilizing controller is characterized by these conditions. Our algorithm generates analytical solutions to the above problem in a recursive manner. In this sense, our algorithm is essentially different from other computational methods pertinent to this problem, such as convex programming. As a result, the algorithm does not involve the issue of convergence and terminates in an a priori known finite number of steps. Thus, the computational complexity is expected to be much less than that of other methods     

A parallel algorithm for generating combinations

A parallel algorithm for generating all combinations of m items out of n given items in lexicographic order is presented. The computational model is a linear systolic array consisting of m identical processing elements. It takes (_mⁿ) time-steps to generate all the (_mⁿ) combinations. Since any processing element is identical and executes the same procedure, it is suitable for VLSI implementation. Based on mathematical induction, such algorithm is proved to be correct.     

A customer threshold property for closed finite queueing networks

We present a new class of finite queues in cyclic networks with production blocking. We show that with a threshold property related to the number of customers in the network, these queues are insensitive to the allocation of buffers and the order of the stations. In addition, some simple and practical, yet effective approximations are presented. Numerical examples have been carried out to demonstrate the efficacy of the approaches.     

A mildly exponential approximation algorithm for the permanent

A new approximation algorithm for the permanent of ann ×n 0,1-matrix is presented. The algorithm is shown to have worst-case time complexity exp(O(n ^1/2 log² n)). Asymptotically, this represents a considerable improvement over the best existing algorithm, which has worst-case time complexity exp((n)).Supported by SERC Grant GR/F 90363; work done in part while visiting DIMACS (Center for Discrete Mathematics and Computer Science).Supported by an NSF PYI grant, with matching equipment grant from the AT&T Foundation; work done in part while visiting DIMACS.     

A recursive algorithm for coprime fractions and Diophantineequations

The computation of coprime fractions for proper rational matrices and the solving of the minimal design problem are important in the design of multivariable systems by using polynomial fractional terms. A recursive algorithm, which fully exploits the shift-invariant property of the generalized resultants, is developed to carry out these computations. A method for solving the Diophantine equation that is based on this algorithm is outlined. This results in a significant reduction in computation as compared to the standard methods involving solution of linear algebraic equations. Some comparisons to existing methods show that the present algorithm is computationally more attractive with regard to efficiency and accuracy     

A recursive search algorithm for statistical disclosure assessment

A new algorithm, SUDA2, is presented which finds minimally unique itemsets i.e., minimal itemsets of frequency one. These itemsets, referred to as Minimal Sample Uniques (MSUs), are important for statistical agencies who wish to estimate the risk of disclosure of their datasets. SUDA2 is a recursive algorithm which uses new observations about the properties of MSUs to prune and traverse the search space. Experimental comparisons with previous work demonstrate that SUDA2 is several orders of magnitude faster, enabling datasets of significantly more columns to be addressed. The ability of SUDA2 to identify the boundaries of the search space for MSUs is clearly demonstrated.     

A division algorithm for polynomial matrices

A new algorithm is presented for directly determining both the quotient and the remainder associated with the division of one polynomial matrix by another. The procedure requires that the denominator matrix be column proper with nonzero column degrees. However, unlike earlier algorithms, only real matrix multiplications are employed; i.e., there is no need for matrix inversions, either explicit or implicit.     

A new algorithm for generating hilbert curves

A new algorithm is described which generates the co-ordinates of the tth point along a Hilbert curve, given the value of the parameter t. The algorithm is expressed in the concurrent programming language occam.