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 present a more efficient CREW PRAM algorithm for integer sorting. This algorithm sorts n integers in {0, 1, 2, ... , n(1/2)} in O(log n)(3/2)/log log n) time and O(n(log n/ log log n)(1/2)) operations. It also sort...
详细信息
We present a more efficient CREW PRAM algorithm for integer sorting. This algorithm sorts n integers in {0, 1, 2, ... , n(1/2)} in O(log n)(3/2)/log log n) time and O(n(log n/ log log n)(1/2)) operations. It also sorts n integers in {0, 1, 2, ..., n - 1} in 0 ((log n)(3/2)/log log n) time and O (n(log n/log log n)1/2 log log log n) operations. Previous best algorithm [15] on both cases has time complexity O(log n) but operation complexity O (n(log n)(1/2)).
We consider a dynamic situation in the weighted bipartite matching problem: edge weights in the input graph are repeatedly updated and we are asked to maintain an optimal matching at any moment. A trivial approach is ...
详细信息
We consider a dynamic situation in the weighted bipartite matching problem: edge weights in the input graph are repeatedly updated and we are asked to maintain an optimal matching at any moment. A trivial approach is to compute an optimal matching from scratch each time an update occurs. In this paper, we show that if each update occurs locally around a single vertex, then a single execution of Dijkstra's algorithm is sufficient to preserve optimality with the aid of a dual solution. As an application of our result, we provide a faster implementation of the envy-cycle procedure for finding an envy-free allocation of indivisible items. Our algorithm runs in O(mn2) time, while the known bound of the original one is O(mn3), where n and m denote the numbers of agents and items, respectively.
Fishburn developed an algorithm to solve a system of m difference constraints whose n unknowns must take values from a set with k real numbers (Fishburn, 2002 [2]). We provide an implementation of Fishburn's algor...
详细信息
Fishburn developed an algorithm to solve a system of m difference constraints whose n unknowns must take values from a set with k real numbers (Fishburn, 2002 [2]). We provide an implementation of Fishburn's algorithm that runs in O(n + km) time.(c) 2023 Elsevier B.V. All rights reserved.
We present an algorithm computing the longest periodic subsequence of a string of length n in O(n7) time with O(n3) space. We obtain improvements when restricting the exponents or extending the search allowing the rep...
详细信息
We present an algorithm computing the longest periodic subsequence of a string of length n in O(n7) time with O(n3) space. We obtain improvements when restricting the exponents or extending the search allowing the reported subsequence to be subperiodic down to O(n2) time and O(n) space. By allowing subperiodic subsequences in the output, the task becomes finding the longest bordered subsequence, for which we devise a conditional lower bound. (c) 2023 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).
A new rewriting code is proposed, that is, the code is suitable for Write Once Memory (woM) devices, for example flash memory, in which the new data may overwrite the old one under the constraint of never changing a 1...
详细信息
A new rewriting code is proposed, that is, the code is suitable for Write Once Memory (woM) devices, for example flash memory, in which the new data may overwrite the old one under the constraint of never changing a 1-bit into a 0-bit. A greedy heuristic is introduced and its compression performance is analyzed. Experimental results show that its efficiency for certain distributions of binary input data may outperform that of state-of-the-art woM codes. Moreover, the technique can be applied to transform any rewriting code for i writing rounds, for any i >= 1, into an enhanced rewriting code for i+1 rounds. (C) 2022 Elsevier B.V. All rights reserved.
Let A, B, and C be three n×n matrices. We investigate the problem of verifying whether AB=C over the ring of integers and finding the correct product AB. Given that C is different from AB by at most k entries, we...
详细信息
We explore definitions of verifiability by Juels et al. (2010), Cortier et al. (2014), and Kiayias et al. (2015). We discover that voting systems vulnerable to attacks can be proven to satisfy each of those definition...
详细信息
We explore definitions of verifiability by Juels et al. (2010), Cortier et al. (2014), and Kiayias et al. (2015). We discover that voting systems vulnerable to attacks can be proven to satisfy each of those definitions and conclude they are unsuitable for the analysis of voting systems. Our results will fuel the exploration for a new definition. (C) 2022 Elsevier B.V. All rights reserved.
作者：
Sokol, DinaCUNY Brooklyn Coll
Dept Comp & Informat Sci 2900 Bedford Ave Brooklyn NY 11210 USA CUNY
Grad Ctr 2900 Bedford Ave Brooklyn NY 11210 USA
This paper extends the problem of 2-dimensional palindrome search into the area of approximate matching. Using the Hamming distance as the measure, we search for 2D palindromes that allow up to k mismatches. We consid...
详细信息
This paper extends the problem of 2-dimensional palindrome search into the area of approximate matching. Using the Hamming distance as the measure, we search for 2D palindromes that allow up to k mismatches. We consider two different definitions of 2D palindromes and describe efficient algorithms for both of them. The first definition implies a square, while the second definition (also known as a centrosymmetric factor), can be any rectangular shape. Given a text of size in (n x m), the time complexity of the first algorithm is O (nm(log m + log n + k)) and for the second algorithm it is O (nm logm + k log k(nm + occ)) where occ is the size of the output. (C) 2020 Elsevier B.V. All rights reserved.
We study resource allocation problems in rooted trees in which demand values are given in the leaves. Single-type resources (weights) are to be assigned in the tree nodes such that the total weight in the rooted path ...
详细信息
We study resource allocation problems in rooted trees in which demand values are given in the leaves. Single-type resources (weights) are to be assigned in the tree nodes such that the total weight in the rooted path from each leaf to the root equals its demand. The goal is to minimize the total costs of the allocated resources. It is known that the linear cost case, i.e., when the cost of a resource is proportional to its weight, is solvable in linear time. In this paper we show that when costs are monotone nondecreasing functions, which reflect, e.g., (dis)economies of scale, the problem becomes intractable, and design for it a fully polynomial time approximation scheme by formulating it as a dynamic program and using the technique of K-approximation sets and functions. (C) 2021 Published by Elsevier B.V.
暂无评论