In this paper, we define the reoptimization variant of the closest substring problem (CSP) under sequence addition. We show that, even with the additional information we have about the problem instance, the problem of finding a closest substring is still NP-hard. We investigate the combinatorial property of optimization problems called self-reducibility. We show that problems that are polynomial-time reducible to self-reducible problems also exhibits the same property. We illustrate this in the context of CSP. We used the property to show that although we cannot improve the approximability of the problem, we can improve the running time of the existing PTAS for CSP.
Due to the hardness results presented in @cite_12 , several other efforts were made to identify for which types of input instances the problem becomes easier to solve. A result in @cite_7 shows that even if the set of input instances is defined over the binary alphabet, we still cannot obtain a practical polynomial-time algorithm for small error bounds. Aside from characterizing input instances, one line of research focused on the of the problem @cite_18 . Based on these studies, it is shown that the problem is , i.e., fixing a parameter such as the pattern length or alphabet size will not make the problem easier to solve.
@cite_18 @cite_7 @cite_12
2132302072 2082173153 2626471773 1987681136
We prove the following about the Nearest Lattice Vector Problem (in any l sub p norm), the Nearest Code-word Problem for binary codes, the problem of learning a halfspace in the presence of errors, and some other problems. 1. Approximating the optimum within any constant factor is NP-hard. 2. If for some spl epsiv >0 there exists a polynomial time algorithm that approximates the optimum within a factor of 2 sup log(0.5- spl epsiv ) sup n then NP is in quasi-polynomial deterministic time: NP spl sube DTIME(n sup poly(log sup n) ). Moreover, we show that result 2 also holds for the Shortest Lattice Vector Problem in the l sub spl infin norm. Improving the factor 2 sup log(0.5- spl epsiv ) sup n to spl radic (dim) for either of the lattice problems would imply the hardness of the Shortest Vector Problem in l sub 2 norm; an old open problem. Our proofs use reductions from few-prover, one-round interactive proof systems, either directly, or through a set-cover problem. > In this paper we study the problem of finding maximally sized subsets of binary strings (codes) of equal length that are immune to a given number @math of repetitions, in the sense that no two strings in the code can give rise to the same string after @math repetitions. We propose explicit number theoretic constructions of such subsets. In the case of @math repetition, the proposed construction is asymptotically optimal. For @math , the proposed construction is within a constant factor of the best known upper bound on the cardinality of a set of strings immune to @math repetitions. Inspired by these constructions, we then develop a prefixing method for correcting any prescribed number @math of repetition errors in an arbitrary binary linear block code. The proposed method constructs for each string in the given code a carefully chosen prefix such that the resulting strings are all of the same length and such that despite up to any @math repetitions in the concatenation of the prefix and the codeword, the original codeword can be recovered. In this construction, the prefix length is made to scale logarithmically with the length of strings in the original code. As a result, the guaranteed immunity to repetition errors is achieved while the added redundancy is asymptotically negligible. We present randomized algorithms that solve Subset Sum and Knapsack instances with n items in O*(20.86n) time, where the O*(·) notation suppresses factors polynomial in the input size, and polynomial space, assuming random read-only access to exponentially many random bits. These results can be extended to solve Binary Linear Programming on n variables with few constraints in a similar running time. We also show that for any constant k≥ 2, random instances of k-Sum can be solved using O(nk-0.5(n)) time and O(logn) space, without the assumption of random access to random bits. Underlying these results is an algorithm that determines whether two given lists of length n with integers bounded by a polynomial in n share a common value. Assuming random read-only access to random bits, we show that this problem can be solved using O(logn) space significantly faster than the trivial O(n2) time algorithm if no value occurs too often in the same list. We develop new techniques for deriving very strong computational lower bounds for a class of well-known NP-hard problems, including weighted satisfiability , dominating set , hitting set , set cover , clique , and independent set . For example, although a trivial enumeration can easily test in time O(nk) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k) no(k) for any function f, even if we restrict the parameter value k to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be Θ(μ(n)) for any reasonable function μ, no algorithm of running time no(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds are also derived for other problems in the above class. Our techniques can be extended to derive computational lower bounds on approximation algorithms for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1 e)no(1 e) for any function f unless an unlikely collapse occurs in parameterized complexity theory.