In this paper, we study exact, exponential-timealgorithms for a variant of the classic LONGEST COMMON SUBSEQUENCE problem called the REPETITION-BOUNDED LONGEST COMMON SUBSEQUENCE problem (or RBLCS, for short): Let an...
详细信息
In this paper, we study exact, exponential-timealgorithms for a variant of the classic LONGEST COMMON SUBSEQUENCE problem called the REPETITION-BOUNDED LONGEST COMMON SUBSEQUENCE problem (or RBLCS, for short): Let an alphabet S be a finite set of symbols and an occurrence constraint C-occ be a function C-occ : S -> N, assigning an upper bound on the number of occurrences of each symbol in S. Given two sequences X and Y over the alphabet S and an occurrence constraint C-occ, the goal of RBLCS is to find a longest common subsequence of X and Y such that each symbol s is an element of S appears at most C-occ(s) times in the obtained subsequence. The special case where C-occ(s) = 1 for every symbol S is an element of S iS known as the REPETITION-FREE LONGEST COMMON SUBSEQUENCE problem (RFLCS) and has been studied previously;e.g., in [1], Adi et al. presented a simple (exponential-time) exact algorithm for RFLCS. However, they did not analyze its time complexity in detail, and to the best of our knowledge, there are no previous results on the running times of any exactalgorithms for this problem. Without loss of generality, we will assume that vertical bar X vertical bar <= vertical bar Y vertical bar and vertical bar X vertical bar = n. In this paper, we first propose a simpler algorithm for RFLCS based on the strategy used in [1] and show explicitly that its running time is O(1.44225(n)). Next, we provide a dynamic programming (DP) based algorithm for RBLCS and prove that its running time is O(1.44225(n)) for any occurrence constraint C-occ, and even less in certain special cases. In particular, for RFLCS, our DP-based algorithm runs in O(1.41422(n)) time, which is faster than the previous one. Furthermore, we prove NP-hardness and APX-hardness results for RBLCS on restricted instances. (C) 2020 Elsevier B.V. All rights reserved.
For more than 30 years Davis-Putnam-style exponential-time backtracking algorithms have been the most common tools used for finding exact solutions of NP-hard problems. Despite of that, the way to analyze such recursi...
详细信息
ISBN:
(纸本)9780898716054
For more than 30 years Davis-Putnam-style exponential-time backtracking algorithms have been the most common tools used for finding exact solutions of NP-hard problems. Despite of that, the way to analyze such recursive algorithms is still far from producing tight worst case running time bounds. The "Measure and Conquer" approach is one of the recent attempts to step beyond such limitations. The approach is based on the choice of the measure of the subproblems recursively generated by the algorithm considered;this measure is used to lower bound the progress made by the algorithm at each branching step. A good choice of the measure can lead to a significantly better worst case time analysis. In this paper we apply "Measure and Conquer" to the analysis of a very simple backtracking algorithm solving the well-studied maximum independent set problem. The result of the analysis is striking: the running time of the algorithm is O(2(0.288n)), which is competitive with the current best time bounds obtained with far more complicated algorithms (and naive analysis). Our example shows that a good choice of the measure, made in the very first stages of exactalgorithms design, can have a tremendous impact on the running time bounds achievable.
For more than 30 years Davis-Putnam-style exponential-time backtracking algorithms have been the most common tools used for finding exact solutions of NP-hard problems. Despite of that, the way to analyze such recursi...
详细信息
ISBN:
(纸本)9780898716054
For more than 30 years Davis-Putnam-style exponential-time backtracking algorithms have been the most common tools used for finding exact solutions of NP-hard problems. Despite of that, the way to analyze such recursive algorithms is still far from producing tight worst case running time *** "Measure and Conquer" approach is one of the recent attempts to step beyond such limitations. The approach is based on the choice of the measure of the subproblems recursively generated by the algorithm considered; this measure is used to lower bound the progress made by the algorithm at each branching step. A good choice of the measure can lead to a significantly better worst case time *** this paper we apply "Measure and Conquer" to the analysis of a very simple backtracking algorithm solving the well-studied maximum independent set problem. The result of the analysis is striking: the running time of the algorithm is O(20.288n), which is competitive with the current best time bounds obtained with far more complicated algorithms (and naive analysis).Our example shows that a good choice of the measure, made in the very first stages of exactalgorithms design, can have a tremendous impact on the running time bounds achievable.
暂无评论