We consider the planted (l,d) motif search problem, which consists of finding a substring of length l that occurs in a set of input sequences {s(1),...,s(n)} with up to d errors, a problem that arises from the need to...
详细信息
We consider the planted (l,d) motif search problem, which consists of finding a substring of length l that occurs in a set of input sequences {s(1),...,s(n)} with up to d errors, a problem that arises from the need to find transcription factor-binding sites in genomic information. We propose a sequence of practical algorithms, which start based on the ideas considered in PMS1. These algorithms are exact, have little space requirements, and are able to tackle challenging instances with bigger d, taking less time in the instances reported solved by exact algorithms. In particular, one of the proposed algorithms, PMSprune, is able to solve the challenging instances, such as (17, 6) and (19, 7), which were not previously reported as solved in the literature.
In this paper, we present improved exact and parameterized algorithms for the maximum satisfiability problem. In particular, we give an algorithm that computes a truth assignment for a boolean formula F satisfying the...
详细信息
In this paper, we present improved exact and parameterized algorithms for the maximum satisfiability problem. In particular, we give an algorithm that computes a truth assignment for a boolean formula F satisfying the maximum number of clauses in time O(1.3247(m)\F\), where m is the number of clauses in F, and \F\ is the sum of the number of literals appearing in each clause in F. Moreover, given a parameter k, we give an O(1.3695(k) + \F\) parameterized algorithm that decides whether a truth assignment for F satisfying at least k clauses exists. Both algorithms improve the previous best algorithms by Bansal and Raman for the problem. (C) 2004 Elsevier B.V. All rights reserved.
In this paper, we present improved exact and parameterized algorithms for the maximum satisfiability problem. In particular, we give an algorithm that computes a truth assignment for a boolean formula F satisfying the...
详细信息
ISBN:
(纸本)3540434003
In this paper, we present improved exact and parameterized algorithms for the maximum satisfiability problem. In particular, we give an algorithm that computes a truth assignment for a boolean formula F satisfying the maximum number of clauses in time O(1.3247(m)\F\), where m is the number of clauses in F, and \F\ is the sum of the number of literals appearing in each clause in F. Moreover, given a parameter k, we give an O(1.3695(k) + \F\) parameterized algorithm that decides whether a truth assignment for F satisfying at least k clauses exists. Both algorithms improve the previous best algorithms by Bansal and Raman for the problem. (C) 2004 Elsevier B.V. All rights reserved.
We study an NP-hard (and MaxSNP-hard) problem in trees-MULTICOMMODITY DEMAND FLOW-dealing with demand flows between pairs of nodes and trying to maximize the value of the routed flows. This problem has been intensivel...
详细信息
We study an NP-hard (and MaxSNP-hard) problem in trees-MULTICOMMODITY DEMAND FLOW-dealing with demand flows between pairs of nodes and trying to maximize the value of the routed flows. This problem has been intensively studied for trees as well as for general graphs mainly from the viewpoint of polynomial-time approximation algorithms. By way of contrast, we provide an exact dynamic programming algorithm for this problem that works well whenever some natural problem parameter is small, a reasonable assumption in several applications. More specifically, we prove fixed-parameter tractability with respect to the maximum number of the input flows at any tree node. (c) 2005 Elsevier B.V. All rights reserved.
We present a first exact study on higher-dimensional packing problems with order constraints. Problems of this type occur naturally in applications such as logistics or computer architecture and can be interpreted as ...
详细信息
We present a first exact study on higher-dimensional packing problems with order constraints. Problems of this type occur naturally in applications such as logistics or computer architecture and can be interpreted as higher- dimensional generalizations of scheduling problems. Using graph- theoretic structures to describe feasible solutions, we develop a novel exact branch and bound algorithm. This extends previous work by Fekete and Schepers;a key tool is a new order- theoretic characterization of feasible extensions of a partial order to a given complementarity graph that is tailor-made for use in a branch- and- bound environment. The usefulness of our approach is validated by computational results.
We derive formulations of the four exact helical Katsevich algorithms in the native cylindrical detector geometry, which allow efficient implementation in modern computed tomography scanners with wide cone beam apertu...
详细信息
We derive formulations of the four exact helical Katsevich algorithms in the native cylindrical detector geometry, which allow efficient implementation in modern computed tomography scanners with wide cone beam aperture. Also, we discuss some aspects of numerical implementation.
The digits of the square root of any real number can be consecutively calculated by hand with the use of a very popular exact algorithm. We show that the application of that algorithm defines a dynamic system in the s...
详细信息
The digits of the square root of any real number can be consecutively calculated by hand with the use of a very popular exact algorithm. We show that the application of that algorithm defines a dynamic system in the sense that it can be reduced to the consecutive iteration of a map H defined in the semi-closed interval [0, 100). We prove that H is chaotic and topologically conjugated to the shift map in the Bernoulli space on 10 symbols. We also exhibit a natural measure for H which is mixing and of maximum entropy. Finally, we adapt the cryptography method proposed by Baptista [M.S. Baptista, Cryptography with chaos, Phys. Lett. A 240 (1998) 50-54] to the dynamics associated with H, advantageously due to its dynamic properties. (c) 2006 Elsevier B.V. All rights reserved.
The currently (asymptotically) fastest algorithm for minimum dominating set on graphs of n nodes is the trivial Omega(2(n)) algorithm which enumerates and checks all the subsets of nodes. In this paper we present a si...
详细信息
The currently (asymptotically) fastest algorithm for minimum dominating set on graphs of n nodes is the trivial Omega(2(n)) algorithm which enumerates and checks all the subsets of nodes. In this paper we present a simple algorithm which solves this problem in O(1.81(n)) time. (C) 2005 Elsevier B.V. All rights reserved.
Viruses compress their genome to reduce space. One of the main techniques is overlapping genes. We model this process by the shortest common superstring problem, that is, we look for the shortest genome which still co...
详细信息
ISBN:
(数字)9783540684237
ISBN:
(纸本)9783540490241
Viruses compress their genome to reduce space. One of the main techniques is overlapping genes. We model this process by the shortest common superstring problem, that is, we look for the shortest genome which still contains all genes. We give an algorithm for computing optimal solutions which is slow in the number of strings but fast (linear) in their total length. This algorithm is used for a number of viruses with relatively few genes. When the number of genes is larger, we compute approximate solutions using the greedy algorithm which gives an upper bound for the optimal solution. We give also a lower bound for the shortest common superstring problem. The results obtained are then compared with what happens in nature. Remarkably, the compression obtained by viruses is quite high and also very close to the one achieved by modern computers.
In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into "rooms", one has to find the mini...
详细信息
ISBN:
(纸本)9783540695134
In this paper we discuss the complexity and approximability of the minimum corridor connection problem where, given a rectilinear decomposition of a rectilinear polygon into "rooms", one has to find the minimum length tree along the edges of the decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give an subexponential time exact algorithm. For the special case of k-outerplanar graphs the running time becomes O(n(3)). We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm.
暂无评论