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.
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.
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.
Given a set of n disjoint rectangular obstacles in the plane whose edges are either vertical or horizontal, we consider the problem of processing rectilinear approximate shortest path queries between pairs of arbitrar...
详细信息
Given a set of n disjoint rectangular obstacles in the plane whose edges are either vertical or horizontal, we consider the problem of processing rectilinear approximate shortest path queries between pairs of arbitrary query points. Our goal is to answer each approximate shortest path query quickly by constructing a data structure that captures path information in the obstacle-scattered plane. We present a data structure for rectilinear approximate shortest path queries that requires O(n log(2) n) time to construct and O(n log n) space. This data structure enables us to report the length of an approximate shortest path between two arbitrary query points in O(log n) time and the actual path in O(log n + L) time, where L is the number of edges of the output path. If the query points are both obstacle vertices, then the length and an actual path can be reported in O(1) and O(L) time, respectively, The approximation factor for the approximate shortest paths that we compute is 3, The previously best known solution to this problem requires O(n log(3) n) time and O(n log(2) n) space to build a data structure, which supports length and actual path queries respectively in O(log(2) n) and O(log(2) n + L) time (regardless of the types of query points);the approximation factor for paths between arbitrary query points is 7.
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.
暂无评论