Search

Splitting is a variance reduction technique widely used to make efficient estimations of the probability of rare events in the simulation of Markovian models. In this article, splitting is applied to improve a well-known method called the Creation Process (CP), used in network reliability estimation. The resulting proposal, called here Splitting/CP, is particularly appropriate in the case of highly reliable networks; i.e., networks for which failure is a rare event. The article introduces the basis of Splitting/CP and presents a set of computational experiments based on network topologies taken from the literature. The results of these experiments show that Splitting/CP is accurate, efficient, and robust and is therefore a valid alternative to the best known methods used in network reliability estimation. [ABSTRACT FROM PUBLISHER]

Abstract: This work presents a novel parallel micro evolutionary algorithm for scheduling tasks in distributed heterogeneous computing and grid environments. The scheduling problem in heterogeneous environments is NP-hard, so a significant effort has been made in order to develop an efficient method to provide good schedules in reduced execution times. The parallel micro evolutionary algorithm is implemented using MALLBA, a general-purpose library for combinatorial optimization. Efficient numerical results are reported in the experimental analysis performed on both well-known problem instances and large instances that model medium-sized grid environments. The comparative study of traditional methods and evolutionary algorithms shows that the parallel micro evolutionary algorithm achieves a high problem solving efficacy, outperforming previous results already reported in the related literature, and also showing a good scalability behavior when facing high dimension problem instances. [Copyright &y& Elsevier]

We propose a polynomial-time algorithm for detecting and deleting classes of network edges which are irrelevant in the evaluation of the Source-to-terminal Diameter Constrained Network reliability parameter. As evaluating this parameter is known to be an NP-hard problem, the proposed procedure may lead to important computational gains when combined with an exact method to calculate the reliability. For illustration, we integrate this algorithm within an exact recursive factorization approach based upon Moskowitz's edge decomposition. Experiments conducted on different real-world topologies confirmed a substantial computational gain, except when highly-dense graphs were tested. [ABSTRACT FROM PUBLISHER]

Several evolutionary algorithms (EAs) applied to a wide class of communication network design problems modelled under the generalized Steiner problem (GSP) are evaluated. In order to provide a fault-tolerant design, a solution to this problem consists of a preset number of independent paths linking each pair of potentially communicating terminal nodes. This usually requires considering intermediate non-terminal nodes (Steiner nodes), which are used to ensure path redundancy, while trying to minimize the overall cost. The GSP is an NP-hard problem for which few algorithms have been proposed. This article presents a comparative study of pure and hybrid EAs applied to the GSP, codified over MALLBA, a general purpose library for combinatorial optimization. The algorithms were tested on several GSPs, and asset efficient numerical results are reported for both serial and distributed models of the evaluated algorithms. [ABSTRACT FROM AUTHOR]

Abstract: Let be a digraph with a distinguished set of terminal vertices and a vertex . We define the -diameter of G as the maximum distance between s and any of the vertices of K. If the arcs fail randomly and independently with known probabilities (vertices are always operational), the diameter-constrained -terminal reliability of G, , is defined as the probability that surviving arcs span a subgraph whose -diameter does not exceed D. The diameter-constrained network reliability is a special case of coherent system models, where the domination invariant has played an important role, both theoretically and for developing algorithms for reliability computation. In this work, we completely characterize the domination of diameter-constrained network models, giving a simple rule for computing its value: if the digraph either has an irrelevant arc, includes a directed cycle or includes a dipath from s to a node in K longer than D, its domination is 0; otherwise, its domination is to the power . In particular this characterization yields the classical source-to-K-terminal reliability domination obtained by Satyanarayana. Based on these theoretical results, we present an algorithm for computing the reliability. [Copyright &y& Elsevier]

This paper proposes a new formulation of the recursive variance-reduction Monte Carlo estimator of the K terminal unreliability parameter of communication systems. This formulation allows significant reduction in the simulation execution time, as demonstrated by experimental results. [ABSTRACT FROM AUTHOR]