102,781 research outputs found
Approximating the Traffic Grooming Problem in Tree and Star Networks
No full textWe consider the problem of grooming paths in all-optical networks with tree topology so as to minimize the switching cost, measured by the
total number of used ADMs. We first present efficient approximation algorithms with approximation factor of 2 ln(d · g) + o(ln(d · g)) for any
fixed node degree bound d and grooming factor g, and 2 ln g + o(ln g) in unbounded degree directed trees, respectively. In the attempt to extend
our results to general undirected trees, we completely characterize the complexity of the problem in star networks by providing polynomial time
optimal algorithms for g 2. While for general topologies, the problem was
known to be NP-hard g not constant, the complexity for fixed values of g was still an open question
Approximating the Traffic Grooming Problem in Tree and Star Networks
No full textWe consider the problem of grooming paths in all-optical networks with tree topology so as to minimize the switching cost, measured by the total number of used ADMs. We first present efficient approximation algorithms with approximation factor of 2ln(delta (.) g) + o(ln(delta (.) g)) for any fixed node degree bound 6 and grooming factor g, and 2 ln g + o(In g) in unbounded degree directed trees, respectively. In the attempt of extending our results to general undirected trees we completely characterize the complexity of the problem in star networks by providing polynomial time optimal algorithms for g 2. While for general topologies the problem was known to be NP-hard g not constant, the complexity for fixed values of g was still an open question
Albert Shalom, R. G. Collingwood, philosophe et historien
No full textDevaux André-A. Albert Shalom, R. G. Collingwood, philosophe et historien. In: Revue Philosophique de Louvain. Quatrième série, tome 69, n°3, 1971. pp. 431-432
Albert Shalom, R. G. Collingwood, philosophe et historien
No full textDevaux André-A. Albert Shalom, R. G. Collingwood, philosophe et historien. In: Revue Philosophique de Louvain. Quatrième série, tome 69, n°3, 1971. pp. 431-432
Approximating the traffic grooming problem
No full textAbstractThe problem of grooming is central in studies of optical networks. In graph-theoretic terms, this can be viewed as assigning colors to the lightpaths so that at most g of them (g being the grooming factor) can share one edge. The cost of a coloring is the number of optical switches (ADMs); each lightpath uses two ADMs, one at each endpoint, and in case g lightpaths of the same wavelength enter through the same edge to one node, they can all use the same ADM (thus saving g−1 ADMs). The goal is to minimize the total number of ADMs. This problem was shown to be NP-complete for g=1 and for a general g. Exact solutions are known for some specific cases, and approximation algorithms for certain topologies exist for g=1. We present an approximation algorithm for this problem. For every value of g the running time of the algorithm is polynomial in the input size, and its approximation ratio for a wide variety of network topologies—including the ring topology—is shown to be 2lng+o(lng). This is the first approximation algorithm for the grooming problem with a general grooming factor g
Shalom: da comunità terapeutica a comunità di vita
No full textRisultati di una ricerca condotta dall'Università Pontificia Salesiana riguardante la Comunità terapeutica Shalom di Palazzolo sull'Oglio (BS
The Traffic Grooming Problem in Optical Networks with Respect to ADMs and OADMs: Complexity and Approximation
No full textAll-optical networks transmit messages along lightpaths in which the signal is transmitted using the same wavelength in all the relevant links. We consider the problem of switching cost minimization in these networks. Specifically, the input to the problem under consideration is an optical network modeled by a graph G, a set of lightpaths modeled by paths on G, and an integer g termed the grooming factor. One has to assign a wavelength (modeled by a color) to every lightpath, so that every edge of the graph is used by at most g paths of the same color. A lightpath operating at some wavelength λ uses one Add/Drop multiplexer (ADM) at both endpoints and one Optical Add/Drop multiplexer (OADM) at every intermediate node, all operating at a wavelength of λ. Two lightpaths, both operating at the same wavelength λ, share the ADMs and OADMs in their common nodes. Therefore, the total switching cost due to the usage of ADMs and OADMs depends on the wavelength assignment. We consider networks of ring and path topology and a cost function that is a convex combination α·|OADMs|+(1−α)|ADMs| of the number of ADMs and the number of OADMs deployed in the network. We showed that the problem of minimizing this cost function is NP-complete for every convex combination, even in a path topology network with g=2. On the positive side, we present a polynomial-time approximation algorithm for the problem
Shalom Comunità di Vita. Analisi pedagogica
No full textAnalisi pedagogica degli esiti della ricerca effettuata dall'Università Pontificia Salesiana sul funzionamento della Comunità Shalom di Palazzolo sull'Oglio (BS)
Adaptive Track-before-detect Algorithms for Targets with Kinematic Constraints in Cluttered Environments
No full text
- …
