1,720,979 research outputs found
Algorithmic strategies for a fast exploration of the TSP 4 -OPT neighborhood
Full text linkWe describe an effective algorithm for exploring the 4 -OPT neighborhood for the Traveling Salesman Problem. 4 -OPT moves change a tour into another by replacing four of its edges. The best move can be found by a Θ (n4) algorithm by complete enumeration, but a Θ (n3) dynamic programming algorithm exists in the literature. Furthermore a Θ (n2) algorithm also exists for a particular subset of symmetric 4 -OPT moves. In this work we describe a new procedure which behaves, on average, slightly worse than a quadratic algorithm over all moves (estimated at O(n2.5)) and like a quadratic algorithm on the symmetric moves. Computational results are reported which show the effectiveness of our strategy compared to other algorithms for finding the best 4 -OPT move, and discuss the strength of the 4 -OPT neighborhood compared to 2- and 3 -OPT
Speeding-up the dynamic programming procedure for the edit distance of two strings
No full textWe describe a way to compute the edit distance of two strings without having to fill the whole dynamic programming (DP) matrix, through a sequence of increasing guesses on the edit distance. If the strings share a certain degree of similarity, the edit distance can be quite smaller than the value of non-optimal solutions, and a large fraction (up to 80–90%) of the DP matrix cells do not need to be computed. Including the method’s overhead, this translates into a speedup factor from 3× up to 30× in the time needed to find the optimal solution for strings of length about 20,000
Bridging fault modeling and simulation for deep submicron CMOS ICs
No full textTesting bridging faults in deep submicron CMOS digital ICs faces new problems because of pushing the technology limits. The growing dispersion of process parameters makes it hard to use conventional bridging fault models for high-quality testing. A new fault model is proposed to account for bridging faults in a way that is independent of electrical parameters and provides a significant coverage metric. Conditions are defined to ensure that (under steady-state conditions) either a fault is detected by a test sequence or it will not give rise to errors for any other input, independently of the actual values of IC parameters. Such a fault model has been implemented in a simulator and validated over combinational benchmarks
Symbolic handling of bridging fault effects
No full textThis paper introduces a new fault simulation methodology based on symbolic handling of fault effects. Boolean variables are related to faulty signals, and fault effects are propagated by computing gate output expressions by means of BDDs. The proposed technique can handle in a single simulation step such faults as resistive bridges, that exhibit a parametric behavior, thus requiring more simulations with conventional techniques
High Quality Test Vectors for Bridging Faults in the Presence of IC's Parameters Variations
No full textThe growing dispersion of parameters in CMOS ICs poses relevant uncertainties on gate output conductances and logic thresholds that affect bridging fault (BF) detection. To analyze the quality of fault simulation and test generation tools using nominal IC parameters, we studied BF detection as a function of the standard deviation of parameters: results show that a single test vector cannot ensure acceptable escape probabilities. Conversely, the minimal number of test vectors providing null escape probability is upper-bounded with respect to variations of parameters, as verified by Monte Carlo electrical-level simulations. We propose a method to derive such minimal test sets for low frequency testing. A fault simulator and a test generator have been developed supporting the search of minimal test sets targeting a null escape probability. © 2007 IEEE
Finding the best 3-opt move in subcubic time
Full text linkGiven a Traveling Salesman Problem solution, the best 3-OPT move requires us to remove three edges and replace them with three new ones so as to shorten the tour as much as possible. No worst-case algorithm better than the Θ(n3 ) enumeration of all triples is likely to exist for this problem, but algorithms with average case O(n3−ɛ ) are not ruled out. In this paper we describe a strategy for 3-OPT optimization which can find the best move by looking only at a fraction of all possible moves. We extend our approach also to some other types of cubic moves, such as some special 6-OPT and 5-OPT moves. Empirical evidence shows that our algorithm runs in average subcubic time (upper bounded by O(n2.5 )) on a wide class of random graphs as well as Traveling Salesman Problem Library (TSPLIB) instances
- …
