The design of efficient algorithms for difficult combinatorial optimization problems remains a challenging field. Many heuristic, meta-heuristic and hyper-heuristic methods exist. In the specialized literature, it is ...
详细信息
ISBN:
(纸本)9781467384186
The design of efficient algorithms for difficult combinatorial optimization problems remains a challenging field. Many heuristic, meta-heuristic and hyper-heuristic methods exist. In the specialized literature, it is observed that for some problems, the combined algorithms have better computational performance than individual performance. However, the automatic combination of the existing methods or the automatic design of new algorithms has received less attention in the literature. In this study, a method to automatically designalgorithms is put into practice for two optimization problems of recognized computational difficulty: the traveling salesman problem and the automatic clustering problem. The new algorithms are generated by means of genetic programming and are numerically evaluated with sets of typical instances for each problem. From an initial population of randomly generated algorithms, a systematic convergence towards the better algorithms is observed after a few hundred generations. Numerical results obtained from the evaluation of each of the designed algorithms suggest that for each set of instances with similar characteristics, specialized algorithms are required.
In this paper, we investigate the optimal assignment problem of cells in PCS (Personal Communication Service) to switches in a wireless ATM network. Given cells and switches on an ATM network (whose locations are fixe...
详细信息
In this paper, we investigate the optimal assignment problem of cells in PCS (Personal Communication Service) to switches in a wireless ATM network. Given cells and switches on an ATM network (whose locations are fixed and known), the problem is grouping cells into clusters and assigning these clusters to the switches in an optimum manner. This problem is modeled as a complex integer programming problem and finding an optimal solution of this problem is NP-complete. A three-phase heuristic algorithm MCMLCF (Maximum cell and minimum local communication first) consisting of Cell Pre-Partitioning Phase, Cell Exchanging Phase, and Cell Migrating Phase, is proposed. First, in the Cell Pre-Partitioning Phase, a three-step procedure (Clustering Step, Packing Step, and Assigning Step) is proposed to group cells into clusters. Second, Cell Exchanging Phase, is proposed to greatly improve the result by repeatedly exchanging two cells in different switches. Finally, Cell Migrating Phase is proposed to reduce cost by repeatedly migrating all cells in a used switch to an empty switch. Experimental results indicate that the proposed algorithm runs efficiently. Comparing the results of the algorithm to a naive heuristic called NSF, we have shown that the computation time is reduced by 30.1%. Experimental results show that Cell Exchanging and Cell Migrating phases can reduce the total cost by 34.1% on average. By comparing the results of the proposed algorithm to the genetic algorithm, the heuristic method came close to optimum - on average within 5%.
We have presented a polynomial-time algorithm based on DynamicProgramming for the Slice- able rectilinear partitioningproblem. The above al- gorithm, though polynomial time, might stillbe re- garded as having a high ...
详细信息
We have presented a polynomial-time algorithm based on DynamicProgramming for the Slice- able rectilinear partitioningproblem. The above al- gorithm, though polynomial time, might stillbe re- garded as having a high complexity for practical appli-cations. Various approaches, such as greedy methods, neural networks,and genetic algorithms can be used to improve the complexity at theexpense of optimality. A greedy variation with simulated annealing ofthe Above algorithm has been implemented for isolating Defect areasin the mask in IBM Microelectronics Di- Vision.
Let G be an undirected 2-edge connected graph with nonnegative edge weights and a distinguished vertex z. For every node consider the shortest cycle containing this node and z in G. The cycle-radius of G is the maximu...
详细信息
Let G be an undirected 2-edge connected graph with nonnegative edge weights and a distinguished vertex z. For every node consider the shortest cycle containing this node and z in G. The cycle-radius of G is the maximum length of a cycle in this set. Let H be a directed graph obtained by directing the edges of C. The cycle-radius of H is similarly defined except that cycles are replaced by directed closed walks. We prove that there exists for every nonnegative edge weight function an orientation H of G whose cycle-radius equals that of G if and only if G is series-parallel. (C) 2011 Elsevier B.V. All rights reserved.
An independent set with 108 vertices in the strong product of four 7-cycles (C-7 boxed times C-7 boxed times C-7 boxed times C-7) is given. This improves the best known lower bound for the Shannon capacity of the grap...
详细信息
An independent set with 108 vertices in the strong product of four 7-cycles (C-7 boxed times C-7 boxed times C-7 boxed times C-7) is given. This improves the best known lower bound for the Shannon capacity of the graph C-7 which is the zero-error capacity of the corresponding noisy channel. The search was done by a computer program using the "simulated annealing" algorithm with a constant time temperature schedule. (C) 2002 Elsevier Science B.V. All rights reserved.
The approximate common interval (ACI) problem, where the multiple genome strings are required to be compared to all other character sets of the other string is discussed. Genomes are considered as strings, with possib...
详细信息
The approximate common interval (ACI) problem, where the multiple genome strings are required to be compared to all other character sets of the other string is discussed. Genomes are considered as strings, with possible repeats of symbols representing paralogous genes, and detect the gene clusters by modeling gene intervals by the set of characters. A specific number of time algorithm that locates all intervals of two strings share the same character set, which also represents the number of the strings. This approximate common interval (ACI) problem for a specific number of strings can be solved in time and space by considering a finite length of every string. A procedure for extracting all maximal character sets of the input strings, and the ACI problem for a single input string and multiple input strings are studied. Graphic representation shows provides a simple and versatile algorithm, supporting the approximate common interval problem.
作者：
KATZ, MJSHARIR, MTEL AVIV UNIV
SCH MATH SCI DEPT COMP SCI IL-69978 TEL AVIV ISRAEL NYU
COURANT INST MATH SCI NEW YORK NY 10012 USA
Given n points in the plane and an integer k, the slope selection problem is to find the pair of points whose connecting line has the kth smallest slope. (In dual setting, given n lines in the plane, we want to find t...
详细信息
Given n points in the plane and an integer k, the slope selection problem is to find the pair of points whose connecting line has the kth smallest slope. (In dual setting, given n lines in the plane, we want to find the vertex of their arrangement with the kth smallest x-coordinate.) Cole et al. have given an O(n log n) solution (which is optimal), using the parametric searching technique of Megiddo. We obtain another optimal (deterministic) solution that does not depend on parametric searching and uses expander graphs instead. Our solution is somewhat simpler than that of [6] and has a more explicit geometric interpretation.
The constrained LCS (CLCS) problem, a recent variant of the longest common subsequence (LCS) problem, has gained much attention. Given two sequences X and Y of lengths n and m, respectively, and the constrained sequen...
详细信息
The constrained LCS (CLCS) problem, a recent variant of the longest common subsequence (LCS) problem, has gained much attention. Given two sequences X and Y of lengths n and m, respectively, and the constrained sequence P of length r, previous research shows that the CLCS problem can be solved by either an 0(nmr)-time algorithm based upon dynamic programming (DP) techniques or an 0(r R log log(n + m))-time Hunt-Szymanski-like algorithm, where,R is the total r umber of ordered pairs of positions at which the two strings match. In this paper, we investigate the case that X, Y and P are all in run-length encoded (RLE) format, where the numbers of runs are N, M and R, respectively. We first show that when the sequences are encoded, the CLCS problem can be solved by a simple algorithm in 0(nmR + nMr + Nmr) time without decompressing the sequences. Then, we propose a more efficient algorithm with 0(NMr + r x min{q(1), q(2)} + q(3)) time, where q(1) and q(2) denote the numbers of elements in the south and east faces of the matched blocks on the first layer, respectively, and q(3) denotes the number of face elements of all fully matched cuboids in the DP lattice. (C) 2012 Elsevier B.V. All rights reserved.
This paper describes an optimal triangulation algorithm for rectangles. We derive lower bounds on the maximum degree of triangulation, and show that our triangulation algorithm matches the lower bounds. Several import...
详细信息
This paper describes an optimal triangulation algorithm for rectangles. We derive lower bounds on the maximum degree of triangulation, and show that our triangulation algorithm matches the lower bounds. Several important observations are also made, including a zig-zag condition that can verify whether a triangulation can minimizes the maximum degree to 4 or not. In addition, this paper identifies the necessary and sufficient condition that there exists a maximum degree 4 triangulation for convex polygons, and gives a linear time checking algorithm. (c) 2005 Elsevier B.V. All rights reserved.
A renewed analysis of Dijkstra's array sorting algorithm Smoothsort showed that the removal of a complexity improved the performance. The resulting algorithm has a worst-case behaviour of order *** N. In the avera...
详细信息
A renewed analysis of Dijkstra's array sorting algorithm Smoothsort showed that the removal of a complexity improved the performance. The resulting algorithm has a worst-case behaviour of order *** N. In the average case, it has more or less the same speed as heapsort. For arrays that are initially almost sorted, it is much faster than heapsort and can compete with quicksort. The correctness is argued by means of invariants. The performance is measured in terms of comparisons and exchanges, both in the analysis of worst-case behaviour and in the experimental data.
暂无评论