Search

We review the state of the art in the problem of counting the number open knight tours, since the publication in internet of a computation of this quantity., Comment: 3 pages

Consider a communication network with a set of sites and a set of links between them. Suppose that the sites are perfect but the links can fail independently from one another. Suppose also that at any given instant t, every link xy is operational or failed with probabilities denoted by p(xy) and 1 - p(xy) respectively. Therefore, there is an \201Coperational subnetwork\201D composed by all the sites and only those links that are operational. Computing the network reliability, i.e. the probability that a given subset K of \201Cdistinguished\201D sites are connected on the operational network yielded at t is known as the K-reliability problem and has been widely studied [1]. When additionaly requiring that the operational network be d-K-connected (i.e. that the distance between any pair of sites of K be bounded by a positive integer d) the problem is known as ddiameter- constrained K-reliability (d-DCKR). In this case the reliability is denoted by Rk(G; d). First introduced in [2], this problem has recently gained relevance because it can model situations where limits exist on the acceptable delay times to propagate traffic (like in voice applications over IP networks) or in the amount of hops that packets can undergo (peer-to-peer networks). The general version is known to belong to the NP-hard complexity class [3]. In this paper we prove

The d-diameter-constrained K-reliability (DCR) problem in networks is an extension of the classical problem of computing the K-reliability (CLR) where the subnetwork resulting from the failure of some edges is operational if and only if all nodes in a set of \201Cterminal nodes\201D K have pairwise distances not greater than a certain integer d. Computing the CLR is NP-hard which has motivated the development of simulation schemes, among which a family of Monte Carlo sampling plans that make use of upper and lower bounds to reduce the variance attained after drawing a given number of samples. The DCR is receiving increasing attention in contexts like video-conferencing and peer-to-peer networks; since it is an extension of the CLR it is also NP-hard. This paper presents Monte Carlo sampling plans based on bounds adapted to the DCR. These plans are described in detail focusing on their requirements and limitations. Test cases are presented evidencing how the diameter constraint and the terminal nodes set size affect the efficiency as well as the higher performance improvements attained by the best-performing methods in the context of DCR when compared to CLR.

We address the serial capacitated economic lot-sizing problem under particular assumptions on the costs and the capacity pattern. We prove that when the involved costs are non-speculative with respect to the transfer to future periods and the capacity pattern is stationary for all levels, the optimal plan for each level can be obtained independently in O(T 3) time. This leads to an O(T 3L) algorithm for the problem with L levels. and the capacity pattern is stationary for all levels, the optimal plan for each level can be obtained independently in O(T 3) time. This leads to an O(T 3L) algorithm for the problem with L levels.

In this paper, we propose a polynomial-time algorithm for detecting and deleting edges of a network 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. Experimental results are shown, corroborating the predicted computational reward, when this reliability preserving algorithm is integrated within an exact factorization approach based upon Moskowitz\2019s edge decomposition theorem and applied to evaluate the Source-to-terminal Diameter Constrained reliability of specific topologies En este trabajo se propone un algoritmo de tiempo polinomial para detectar y eliminar aristas de una red que son irrelevantes para el cálculo del parámetro de confiabilidad fuente-terminal con restricciones de diámetro en una red. Como la evaluación de este parámetro es un problema NP-difícil, el procedimiento propuesto puede resultar en una importante ganancia computacional cuando se combina con un método exacto para calcular la confiabilidad. Los resultados experimentales que se incluyen corroboran la ganancia computacional predicha, cuando el método de reducción es integrado dentro de un enfoque de factorización exacto, basado en el teorema de descomposición en aristas de Moskowitz, y utilizado para evaluar la confiabilidad con restricciones de dimetro de algunas topologías específicas.

Splitting is a variance reduction technique, widely used to improve the efficiency of markovian systems simulations. In this report Splitting is successfully adapted to the reliability network estimation problem by means of a well-known model based on the so called Creation Process. A network model based on the Creation Process is revisited, a brief review of Splitting in a general setting is introduced and afterwards Splitting is applied to the estimation of the source terminal network unreliability by means of the Creation Process Model. Finally a set of experiments to assess the performance of Splitting in this task, are shown.

In this paper we consider the evaluation of a well Known K-network unreliability parameter by means of a new RVR Monte-Carlo method. It is based on seres-parellel reductions and a conditioning procedure using pathsets and cutsets for recursively changing the original problem into the unreliability problem for a smaller network. We illustrate by experimental results that the proposed method has good behavior in rare event cases and offers significant speed-ups over other state-of-the art variance-reduction techniques.

We give an estimate of the number of geometrically distinct open tours $\G$ for a knight on a chessboard. We use a randomization of Warnsdorff rule to implement importance sampling in a backtracking scheme, correcting the observed bias of the original rule, according to the proposed principle that ``most solutions follow Warnsdorff rule most of the time''. After some experiments in order to test this principle, and to calibrate a parameter, interpreted as a distance of a general solution from a Warnsdorff solution, we conjecture that $\G=1.22\times 10^{15}$., Comment: 8 pages. See also http://www.cmat.edu.uy/~mordecki/articles

Content networks are usually virtual networks based over the IP infrastructure of Internet or of a corporative network, which use mechanisms to allow accessing a content when there is no fixed, single, link between the content and the host or the hosts where this content is located. Even more, the content is usually subject to re-allocations, replications, and even deletions from the different nodes of the network. In the last years many different kinds of content networks have been developed and deployed in widely varying contexts: they include peer-to-peer networks, collaborative networks, cooperative Web caching, content distribution networks, subscribe-publish networks, content-based sensor networks, backup networks, distributed computing, instant messaging, and multiplayer games. As a general rule, every content network is actually a knowledge network, where the knowledge is the information about the location of the nodes where each specific content is to be found: this is "meta-information", in the sense of being the information about the information contents themselves. The objective of the network is to be able to answer each content query with the most complete possible set of nodes where this content is to be found; this corresponds to discover the content location in the most effective and efficient possible way. As both nodes and contents are continuously going in and out of the network, the task of maintaining updated the network meta-information is very difficult and represents an important communication cost. In this context, cache nodes are used to hold the available meta-information; as this information is continuously getting outdated, the cache nodes must decide when to discard it, which means increasing communication overhead for the sake of improving the quality of the answers. The policy employed for determining these cache expiration dates have a large impact in the performance of a network; this problem is related but at the same time

Let G=(V,E) be a digraph with a distinguished set of terminal vertices K in V and a vertex s in K. We define the s,K-diameter of G as the maximum distance between s and any of vertices of K. If the arcs fail randomly and independently with known probabilities (vertices are always operational), the Diameter-constrained s,K-terminal reliability of G, R_\{s,K\}(G,D) is defined as the probability that surviving arcs span a subgraph whose s,K-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 edge, includes a dicycle or includes a dipath from $s$ to a node in K longer than D, its domination is 0; otherwise, its domination is -1 to the power |E|-|V|+1.

This paper is a first step in the direction of charging telecommunication network access based on the reliability of end-to-end paths. Indeed, in the literature congestion pricing is usually considered as the solution to address the needs of quality-of-service-demanding new applications such as multimedia. Nevertheless, with the widespread diffusion and high capacities of optical fiber, some authors have argued that this pricing scheme will not have to be applied, as capacity will still be ahead of demand. In this paper, we introduce a new direction, noting that even when there is spare capacity, availability can still be a concern. We argue that a charging scheme depending on reliability could be interesting and illustrate how it could be implemented. We also provide a genetic algorithm aiming at extending the network so that the provider's revenue is maximized. We observe the behavior of our method over a specific network topology, and study the robustness of the solution with respect to the problem data.

The greedy randomized adaptive search procedure (GRASP) is a well-known metaheuristic for combinatorial optimization. In this work, we introduce a GRASP for designing a survivable Wide Area Network backbone. The algorithm builds topologies which comply with heterogeneous node-connectivity requirements. This work is motivated by the need of designing a low-cost backbone network which can survive to failures in switch sites as well as in the connection lines. The method is applied to a set of problem instances with different connectivity requirements, obtaining results which appear promising.

Nowadays, there is an increasing number of computer intensive applications, which exceed the capacity of a standard stand-alone computer. An alternative is to parallelize the application and run it in a cluster; there has been much work in this sense, specially in platforms and tools to build a cluster from commodity components, and to develop parallel applications. One of the problems that subsist is the one faced by the analyst when designing a new application in this environment. He must solve the trade-off between the cost of building the cluster, and the application's running time; if he under-dimensions the cluster, the running time might be too long; if he over-dimensions it, the cost might not be acceptable. This work presents an example of how analytical performance models can be applied in this context. In particular, we develop a parallel implementation of a combinatorial optimization heuristic for solving the Steiner Tree Problem, and a Petri net model which can be used to predict the running time of the application on a cluster of PCs, on the basis of measurements on stand-alone equipment. The model is validated experimentally, showing that it adequately predicts optimistic and pessimistic bounds for the measured running time.

Consider a network where the links are subject to random, independent failures. The diameter constrained network reliability parameter R(G,K,D) measures the probability that the set K of terminals of the network are linked by operational paths of length less or equal to D. This parameter generalizes the classical network reliability, allowing to reflect performance objectives that restrict the maximum length of a path in the network. This is the case, for example, when the transmissions between every two terminal nodes in the subset K are required to experience a maximum delay D.T (where T is the delay experienced at a single node or link); then the probability that after random failures of the communication links, the surviving network meets the maximum delay requirement is the diameter constrained reliability R(G,K,D). This paper defines the diameter constrained network reliability, and gives a formulation in terms of events corresponding to the operation of the (length constrained) paths of the network. Based on this formulation, the exact value of the diameter constrained reliability is derived, for the special case where K=\{s,t\} and the upper bound D of the path length is 2. For other values of K and D an exact evaluation algorithm based on a factorization approach is proposed. As this algorithm has exponential worst case complexity, upper and lower bounds for K=\{s,t\} are developed, which in some cases may be used instead of the exact value

Ant Systems (AS) is a recently proposed meta-heuristic inspired on biological behaviors, which has been applied to a variety of combinatorial optimization problems, including the QAP (Quadratic Assignment Problems). In this work, we have studied the adaptation of the Ant Systems meta-heuristic to two different real-life assignment problems, which appear in educational institutions: the timetabling problem (assigning courses to classrooms and times), and the assignment of final proyects to students. There is no standard definition for these problems, as in each institution the rules and objectives are different. We have been successful in adapting. AS to tackle these problems as defined by our institution rules, showing the adaptability of this meta-heuristic to complex, real-life problems. In both cases the AS meta-heuristic obtained good quality solutions (in the timetabling case, at the cost of longer running times).

Una red de comunicaciones es un sistema compuesto por un conjunto de centros que reciben y envían información, y por un conjunto de conexiones que transportan esa información. La capacidad de una red de comunicaciones para resistir a posibles fallos de algunos de sus componentes se evalúa a través de distintas métricas de confiabilidad. Uno de los problemas que se plantean durante el diseño de una red, es el de elegir su topología precisamente para asegurar al máximo las comunicaciones. En este trabajo, abordamos una versión de este problema, en la que el objetivo es encontrar una topología más confiable a partir de una red dada por el usuario. La metodología empleada corresponde a la metaheurística "simulated annealing", de reciente utilización en el campo de la optimización combinatoria.