This paper presents a new method and a constraint-based objective function to solve two problemsrelated to the design of optical telecommunication networks, namely the Synchronous Optical Net-work Ring Assignment Problem (SRAP) and the Intra-ring Synchronous Optical Network DesignProblem (IDP). These network topology problems can be represented as a graph partitioning withcapacity constraints as shown in previous works. We present here a new objective function and anew local search algorithm to solve these problems. Experiments conducted in C
In @cite_4 the SRAP problem is considered. They propose three greedy algorithms with different heuristics, the , the and the . The first two algorithms start by assigning each node to a different ring. At each iteration they reduce the number of rings by merging two rings @math and @math if @math is a feasible ring for the capacity constraint. In the edge-based heuristic, the two rings with the maximum weight edge are merged. While in the cut-based heuristic, the two rings with the maximum total weight of the edges with one endpoint in each of them, are merged. Algorithm shows the pseudo code for the edge-based heuristic.
@cite_4
2002547394
We consider the problem of interconnecting a set of customer sites using bidirectional SONET rings of equal capacity. Each site is assigned to exactly one ring and a special ring, called the federal ring, interconnects the other rings together. The objective is to minimize the total cost of the network subject to a ring capacity limit where the capacity of a ring is determined by the total bandwidth required between sites assigned to the same ring plus the total bandwidth request between these sites and sites assigned to other rings.We present exact, integer-programming based solution techniques and fast heuristic algorithms for this problem. We compare the results from applying the heuristic algorithms with those produced by the exact methods for real-world as well as randomly generated problem instances. We show that two of the heuristics find solutions that cost at most twice that of an optimal solution. Empirical evidence indicates that in practice the algorithms perform much better than their theoretical bound and often find optimal solutions. In this paper, we deal with a network design problem arising from the deployment of synchronous optical networks (SONET), a standard of transmission using optical fiber technology. The problem is to find an optimal clustering of traffic demands in the network such that the total number of node assignments (and, hence, add-drop multiplexer equipment requirements) is minimized, while satisfying the ring capacity and node cardinality constraints. This problem can be conceptualized as an edge-capacitated graph partitioning problem with node cardinality constraints. We formulate the problem as a mixed-integer programming model and develop a new branch-and-cut algorithm along with preprocessing routines for optimally solving the problem. We also prescribe an effective heuristic procedure. Promising computational results are obtained using the proposed method. For a pattern graph @math on @math nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of @math in a given large graph @math on @math nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. Our results include the following: 1. The number of copies of an @math with an independent set of size @math can be computed exactly in @math time and @math space, or in @math time and @math space. (The @math notation omits @math factors.) To obtain these algorithms we provide fast algorithms for computing the permanent of a @math matrix over rings and semirings. 2. The number of copies of any @math having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in @math time, where @math is the matrix multiplication exponent and @math is divisible by @math . Similar results hold for other values of @math . Also, the number... We study computationally hard combinatorial problems arising from the important engineering question of how to maximize the number of connections that can be simultaneously served in a wavelength division ultiplexing (WDM) optical network. In such networks, WDM technology can satisfy a set of connections by computing a route and assigning a wavelength to each connection so that no two connections routed through the same fiber are assigned the same wavelength. Each fiber supports a limited number of @math wavelengths and in order to fully exploit the parallelism provided by the technology, one should select a set of connections of maximum cardinality which can be satisfied using the available wavelengths. This is known as the maximum routing and path coloring (maxRPC) problem. Our main contribution is a general analysis method for a class of iterative algorithms for a more general coloring problem. A lower bound on the benefit of the solution computed by such an algorithm in terms of the optimal benefit and the number of available wavelengths is given by a benefit-revealing linear program. We apply this method to maxRPC in both undirected and bidirected rings to obtain upper bounds on the approximation ratio of several algorithms. The best bounds obtained are @math and @math for undirected and bidirected rings; these results improve known bounds of @math and @math , respectively. Our results extend to multifiber ring networks and also apply to the maximum path coloring (maxPC) problem, where paths instead of connection requests are given as part of the input. We also study the profit version of maxPC in rings where each path has a profit and the objective is to satisfy a set of paths of maximum total profit. We present an algorithm based on linear programming and randomized rounding with approximation ratio 1.49015, improving on the @math bound obtained by a simple iterative algorithm. Consider a set of mobile robots placed on distinct nodes of a discrete, anonymous, and bidirectional ring. Asynchronously, each robot takes a snapshot of the ring, determining the size of the ring and which nodes are either occupied by robots or empty. Based on the observed configuration, it decides whether to move to one of its adjacent nodes or not. In the first case, it performs the computed move, eventually. This model of computation is known as Look-Compute-Move. The computation depends on the required task. In this paper, we solve both the well-known Gathering and Exclusive Searching tasks. In the former problem, all robots must simultaneously occupy the same node, eventually. In the latter problem, the aim is to clear all edges of the graph. An edge is cleared if it is traversed by a robot or if both its endpoints are occupied. We consider the exclusive searching where it must be ensured that two robots never occupy the same node. Moreover, since the robots are oblivious, the clearing is perpetual, i.e., the ring is cleared infinitely often. In the literature, most contributions are restricted to a subset of initial configurations. Here, we design two different algorithms and provide a characterization of the initial configurations that permit the resolution of the problems under very weak assumptions. More precisely, we provide a full characterization (except for few pathological cases) of the initial configurations for which gathering can be solved. The algorithm relies on the necessary assumption of the local-weak multiplicity detection. This means that during the Look phase a robot detects also whether the node it occupies is occupied by other robots, without acquiring the exact number. For the exclusive searching, we characterize all (except for few pathological cases) aperiodic configurations from which the problem is feasible. We also provide some impossibility results for the case of periodic configurations. It is well known that at low-bit-rate block discrete cosine transform compressed image exhibits visually annoying blocking and ringing artifacts. In this paper, we propose a noniterative, wavelet-based deblocking algorithm to reduce both types of artifacts. The algorithm exploits the fact that block discontinuities are constrained by the dc quantization interval of the quantization table, as well as the behavior of wavelet modulus maxima evolution across wavelet scales to derive appropriate threshold maps at different wavelet scales. Since ringing artifacts occur near strong edges, which can be located either along block boundaries or within blocks, suppression of block discontinuities does not always reduce ringing artifacts. By exploiting the behavior of ringing artifacts in the wavelet domain, we propose a simple yet effective method for the suppression of such artifacts. The proposed algorithm can suppress both block discontinuities and ringing artifacts effectively while preserving true edges and textural information. Simulation results and extensive comparative study with both iterative and noniterative methods reported in the literature have shown the effectiveness of our algorithm. Ringing is an annoying artifact frequently encountered in low bit-rate transform and subband decomposition based compression of different media such as image, intra frame video and graphics. A mathematical morphology based post-processing algorithm is presented in this paper for image ringing artifact suppression. First, we use binary morphological operators to isolate the regions of an image where the ringing artifact is most prominent to the human visual system (HVS) while preserving genuine edges and other (high-frequency) fine details present in the image. Then, a gray-level morphological nonlinear smoothing filter is applied to the unmasked regions of the image under the filtering mask to eliminate ringing within this constraint region. To gauge the effectiveness of this approach, we propose an HVS compatible objective measure of the ringing artifact. Preliminary simulations indicate that the proposed method is capable of significantly reducing the ringing artifact on both subjective and objective basis. For a pattern graph H on k nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of H in a given large graph G on n nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. Our results include: The number of copies of an H with an independent set of size s can be computed exactly in O*(2s nk-s+3) time. A minimum weight copy of such an H (with arbitrary real weights on nodes and edges) can be found in O(4s+o(s) nk-s+3) time. (The O* notation omits (k) factors.) These algorithms rely on fast algorithms for computing the permanent of a k x n matrix, over rings and semirings. The number of copies of any H having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in O(nω k 3 + n2k 3+o(1)) time, where ω 0, unless the 3SUM problem on N numbers can be solved in O(N2 - e) time. This suggests that the edge-weighted problem is much harder than its node-weighted version. We consider two variants of the task of spreading a swarm of agents uniformly on a ring graph. Ant-like oblivious agents having limited capabilities are considered. The agents are assumed to have little memory, they all execute the same algorithm and no direct communication is allowed between them. Furthermore, the agents do not possess any global information. In particular, the size of the ring (n) and the number of agents in the swarm (k) are unknown to them. The agents are assumed to operate on an unweighted ring graph. Every agent can measure the distance to his two neighbors on the ring, up to a limited range of V edges. The first task considered, is dynamical (i.e. in motion) uniform deployment on the ring. We show that if either the ring is unoriented, or the visibility range is less than @?n [email protected]?, this is an impossible mission for the agents. Then, for an oriented ring and V>[email protected]?n [email protected]?, we propose an algorithm which achieves the deployment task in optimal time. The second task discussed, called quiescent spread, requires the agents to spread uniformly over the ring and stop moving. We prove that under our model, in which every agent can measure the distance only to his two neighbors, this task is impossible. Subsequently, we propose an algorithm which achieves quiescent but only almost uniform spread. The algorithms we present are scalable and robust. In case the environment (the size of the ring) or the number of agents changes during the run, the swarm adapts and re-deploys without requiring any outside interference. This paper considers two problems that arise in the design of optical telecommunication networks when a ring-based topology is adopted, namely the SONET Ring Assignment Problem and the Intraring Synchronous Optical Network Design Problem. We show that these two network topology problems correspond to graph partitioning problems with capacity constraints: the first is a vertex partitioning problem, while the latter is an edge partitioning problem. We consider solution methods for both problems, based on metaheuristic algorithms. We first describe variable objective functions that depend on the transition from one solution to a neighboring one, then we apply several diversification and intensification techniques including Path Relinking, eXploring Tabu Search and Scatter Search. Finally we propose a diversification method based on the use of multiple neighborhoods. A set of extensive computational results is used to compare the behaviour of the proposed methods and objective functions. In this work we consider temporal networks, i.e. networks defined by a labeling ( ) assigning to each edge of an underlying graphG a set of discrete time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on path problems of temporal networks. In particular, we consider time-respecting paths, i.e. paths whose edges are assigned by ( ) a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a natural analogue of Menger’s theorem holding for arbitrary temporal networks. Finally, we propose two cost minimization parameters for temporal network design. One is the temporality of G, in which the goal is to minimize the maximum number of labels of an edge, and the other is the temporal cost of G, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some connectivity constraint. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees. We study the localization problem in the ring: a collection of @math n anonymous mobile robots are deployed in a continuous ring of perimeter one. All robots start moving at the same time with arbitrary velocities, starting in clockwise or counterclockwise direction around the ring. The robots bounce against each other according to the principles of conservation of energy and momentum. The task of each robot is to find out, in finite time, the initial position and the initial velocity of every deployed robot. The only way that robots perceive the information about the environment is by colliding with their neighbors; robots have no control of their walks or velocities moreover any type of communication among them is not possible. The configuration of initial positions of robots and their speeds is considered feasible, if there is a finite time, after which every robot starting at this configuration knows initial positions and velocities of all other robots. It was conjectured in (2012) that if the principles of conservation of energy and momentum were assumed and the robots had arbitrary velocities, the localization problem might be solvable. We prove that this conjecture is false. We show that if @math v0,v1,?,vn-1 are the velocities of a given robot configuration @math S, then @math S is feasible if and only if @math vi?v¯ for all @math 0≤i≤n-1, where @math v¯=v0+?+vn-1n. To figure out the initial positions of all robots no more than @math 2min0≤i≤n-1|vi-v¯| time is required. It is shown that, over an arbitrary ring, the functions computed by polynomial-size algebraic formulas are also computed by polynomial-length algebraic straight-line programs that use only three registers. This was previously known for Boolean formulas [D. A. Barrington, J. Comput. System Sci., 38 (1989), pp. 150–164], which are equivalent to algebraic formulas over the ring @math . For formulas over arbitrary rings, the result is an improvement over previous methods that require the number of registers to be logarithmic in the size of the formulas in order to obtain polynomial-length straight-line programs. Moreover, the straight-line programs that arise in these constructions have the property that they consist of statements whose actions on the registers are linear and bijective. A consequence of this is that the problem of determining the iterated product of @math matrices is complete (under P-projections) for algebraic @math . Also, when the ring is @math , the programs that arise in the c... Traceroute is a widely used program for computing the topology of any network in the Internet. Using Traceroute, one starts from a node and chooses any other node in the network. Traceroute obtains the sequence of nodes that occur between these two nodes, as specified by the routing tables in these nodes. Each use of Traceroute in a network produces a trace of nodes that constitute a simple path in this network. In every trace that is produced by Traceroute, each node occurs either by its unique identifier, or by the anonymous identifier"*". In this paper, we introduce the first theory aimed at answering the following important question. Is there an algorithm to compute the topology of a network N from a trace set T that is produced by using Traceroute in network N , assuming that each edge in N occurs in at least one trace in T , and that each node in N occurs by its unique identifier in at least one trace in T ? We prove that the answer to this question is "No" if N is an even ring or a general network. However, it is "Yes" if N is a tree or an odd ring. The answer is also "No" if N is mostly-regular, but "Yes" if N is a mostly-regular even ring. Abstract We present two algorithms to compute the endomorphism ring of an ordinary elliptic curve E defined over a finite field F q . Under suitable heuristic assumptions, both have subexponential complexity. We bound the complexity of the first algorithm in terms of log q , while our bound for the second algorithm depends primarily on log | D E | , where D E is the discriminant of the order isomorphic to End ( E ) . As a byproduct, our method yields a short certificate that may be used to verify that the endomorphism ring is as claimed. The paper considers the complexity of bilinear forms in a noncommutative ring. The dual of a computation is defined and applied to matrix multiplication and other bilinear forms. It is shown that the dual of an optimal computation gives an optimal computation for a dual problem. An @math by @math matrix product is shown to be the dual of an @math by @math or an @math by @math matrix product, implying that each of the matrix products requires the same number of multiplications to compute. Finally, an algorithm for computing a single bilinear form over a noncommutative ring with a minimum number of multiplications is derived by considering a dual problem. We consider requests for capacity in a given tree network T e (V, E) where each edge e of the tree has some integer capacity ue. Each request f is a node pair with an integer demand df and a profit wf which is obtained if the request is satisfied. The objective is to find a set of demands that can be feasibly routed in the tree and which provides a maximum profit. This generalizes well-known problems, including the knapsack and b-matching problems. When all demands are 1, we have the integer multicommodity flow problem. [1997] had shown that this problem is NP-hard and gave a 2-approximation algorithm for the cardinality case (all profits are 1) via a primal-dual algorithm. Our main result establishes that the integrality gap of the natural linear programming relaxation is at most 4 for the case of arbitrary profits. Our proof is based on coloring paths on trees and this has other applications for wavelength assignment in optical network routing. We then consider the problem with arbitrary demands. When the maximum demand dmax is at most the minimum edge capacity umin, we show that the integrality gap of the LP is at most 48. This result is obtained by showing that the integrality gap for the demand version of such a problem is at most 11.542 times that for the unit-demand case. We use techniques of Kolliopoulos and Stein [2004, 2001] to obtain this. We also obtain, via this method, improved algorithms for line and ring networks. Applications and connections to other combinatorial problems are discussed. In this paper, we study the benefits of using tunable transceivers for reducing the required number of electronic ports in wavelength-division-multiplexing time-division multiplexing optical networks. We show that such transceivers can be used to efficiently "groom" subwavelength traffic in the optical domain and so can significantly reduce the amount of terminal equipment needed compared with the fixed-tuned case. Formulations for this "tunable grooming" problem are provided, where the objective is to schedule transceivers so as to minimize the required number of ports needed for a given traffic demand. We establish a relationship between this problem and edge colorings of graphs which are determined by the offered traffic. Using this relationship, we show that, in general, this problem is NP-complete, but we are able to efficiently solve it for many cases of interest. When the number of wavelengths in the network is not limited, each node is shown to only require the minimum number of transceivers (i.e., no more transceivers than the amount of traffic that it generates). This holds regardless of the network topology or traffic pattern. When the number of wavelengths is limited, an analogous result is shown for both uniform and hub traffic in a ring. We then develop a heuristic algorithm for general traffic that uses nearly the minimum number of transceivers. In most cases, tunable transceivers are shown to reduce the number of ports per node by as much as 60 . We also consider the case where traffic can dynamically change among an allowable set of traffic demands. Tunability is again shown to significantly reduce the port requirement for a nonblocking ring, both with and without rearrangements. The present paper shows a mathematical formalization of---as well as algorithms and software for computing---volume-optimal cycles. Volume-optimal cycles are useful for understanding geometric features appearing in a persistence diagram. Volume-optimal cycles provide concrete and optimal homologous structures, such as rings or cavities, on a given dataset. The key idea is the optimality on a @math -chain complex for a @math th homology generator. This optimality formalization is suitable for persistent homology. We can solve the optimization problem using linear programming. For an alpha filtration on @math , volume-optimal cycles on an @math st persistence diagram are more efficiently computable using a merge-tree algorithm. The merge-tree algorithm also provides a tree structure on the diagram containing richer information than volume-optimal cycles. The key mathematical idea used here is Alexander duality. We study the SMARTNet (scalable multichannel adaptable ring terabit network), an optical wavelength-division packet-switching meshed-ring network employing wavelength routers. We investigate the ways to configure these wavelength routers in adapting to the underlying traffic matrix. One heuristic algorithm for this purpose is developed. We show that for any traffic matrix, the throughput performance of the SMARTNet employing wavelength cross-connect routing devices is upper bounded by that of a corresponding meshed-ring network employing store-and-forward switching devices. The difference diminishes as the number of employed wavelengths increases. Furthermore, for a specific meshed-ring: topology, we show that the above upper bound throughput level is achievable under uniform traffic loading at even a small number of wavelengths. Under nonuniform traffic loading, we show that a throughput level equal to 80 to 90 of the upper bound value can be achieved with a small number (five to seven) of wavelengths.