This work introduces novel parallel methods for weighted longest common subsequence (WLCS) and its generalization, allsubstrings WLCS. Previous work developed efficient algorithms for these problems via Monge matrix m...
详细信息
ISBN:
(纸本)9783030856656;9783030856649
This work introduces novel parallel methods for weighted longest common subsequence (WLCS) and its generalization, allsubstrings WLCS. Previous work developed efficient algorithms for these problems via Monge matrix multiplication, which is a limiting factor for further improvement. Diverging from these approaches, we relax the algorithm's optimality guarantee in a controlled way, using a different, natural dynamic program which can be sketched and solved in a divideand-conquer manner that is efficient to parallelize. Additionally, to compute the base case of our algorithm, we develop a novel and efficient method for all-substrings WLCS inspired by previous work on unweighted all-substrings LCS, exploiting the typically small range of weights. Our method fits in most parallel models of computation, including the PRAM and the BSP model. To the best of our knowledge this is the fastest (1 -epsilon)-approximation algorithm for all-substrings WLCS and WLCS in BSP. Further, this is the asymptotically fastest parallel algorithm for weighted LCS as the number of processors increases.
approximation via sampling is a widespread technique whenever exact solutions are too expensive. In this paper, we present techniques for an efficient parallelization of adaptive (a.k.a. progressive) sampling algorith...
详细信息
ISBN:
(纸本)9783030294007;9783030293994
approximation via sampling is a widespread technique whenever exact solutions are too expensive. In this paper, we present techniques for an efficient parallelization of adaptive (a.k.a. progressive) sampling algorithms on multi-threaded shared-memory machines. Our basic algorithmic technique requires no synchronization except for atomic load-acquire and store-release operations. It does, however, require O(n) memory per thread, where n is the size of the sampling state. We present variants of the algorithm that either reduce this memory consumption to O(1) or ensure that deterministic results are obtained. Using the KADABRA algorithm for betweenness centrality (a popular measure in network analysis) approximation as a case study, we demonstrate the empirical performance of our techniques. In particular, on a 32-core machine, our best algorithm is 2.9x faster than what we could achieve using a straightforward OpenMP-based parallelization and 65.3x faster than the existing implementation of KADABRA.
In this paper we present improved approximationalgorithms for two classes of maximization problems defined in Barland et al. (J. Comput. System Sci. 57(2) (1998) 144). Our factors of approximation substantially impro...
详细信息
In this paper we present improved approximationalgorithms for two classes of maximization problems defined in Barland et al. (J. Comput. System Sci. 57(2) (1998) 144). Our factors of approximation substantially improve the previous known results and are close to the best possible. On the other hand, we show that the approximation results in the framework of Barland et al. hold also in the parallel setting, and thus we have a new common framework for both computational settings. We prove almost tight non-approximability results, thus solving a main open question of Barland et al. We obtain the results through the constraint satisfaction problem over multi-valued domains, for which we develop approximationalgorithms and show non-approximability results. Our parallel approximation algorithms are based on linear programming and random rounding;they are better than previously known sequential algorithms. The non-approximability results are based on new recent progress in the fields of probabilistically checkable proofs and multi-prover one-round proof systems. (c) 2004 Elsevier B.V. All rights reserved.
The HIGH DEGREE SUBGRAPH problem is to find a subgraph H of a graph G such that the minimum degree of H is as large as possible. This problem is known to be P-hard so that parallel approximation algorithms are very im...
详细信息
The HIGH DEGREE SUBGRAPH problem is to find a subgraph H of a graph G such that the minimum degree of H is as large as possible. This problem is known to be P-hard so that parallel approximation algorithms are very important for it. Our first goal is to determine how effectively the approximation algorithm based on a well-known extremal graph result parallelizes. In particular, we show that two natural decision problems associated with this algorithm are P-complete: these results suggest that the parallel implementation of the algorithm itself requires more sophisticated techniques. Successively, we study the HIGH DEGREE SUBGRAPH problem for random graphs with any edge probability function and we provide different parallel approximation algorithms depending on the type of this function. (C) 1998-Elsevier Science B.V. All rights reserved.
A systolic based parallelapproximation algorithm that obtains solutions to the 1-D Bin Packing problem is presented. The algorithm has an asymptotic error bound of 1.5 and time complexity O(n). An experimental study ...
详细信息
A systolic based parallelapproximation algorithm that obtains solutions to the 1-D Bin Packing problem is presented. The algorithm has an asymptotic error bound of 1.5 and time complexity O(n). An experimental study demonstrates that the heuristic offers improved packing and execution performance over parallelizations of two well-known serial algorithms.
暂无评论