The Complexity of Polynomial-Time Approximation

In 1996 Khanna and Motwani proposed three logic-based optimization problems constrained by planar structure, and offered the hypothesis that these putatively fundamental problems might provide insight into characterizing the class of optimization problems that admit a polynomial-time approximation scheme (PTAS). The main contribution of this paper is to explore this program from the point of view of parameterized complexity. Problems of optimization are naturally parameterized by the parameter k = 1/ε. An optimization problem admits a PTAS if and only if there is an algorithm Φ, that, given an input of size n, and a parameter value k = 1/ε, produces a solution that is within a multiplicative factor of (1+ ε) of optimal, in a running time that is polynomial for every fixed value of ε. This definition admits the possibility that the degree of the polynomial that bounds the running time of Φ may increase, even quite dramatically, as a function of k = 1/ε. In fact, amongst the PTASs that are currently known, for an error of 20%, polynomial-time bounds no better than O(n²⁰⁰⁰) are quite common. Viewing k = 1/ε as a problem parameter, in the sense of parameterized complexity, leads naturally to the question of whether an efficient PTAS (EPTAS) might be possible for a given optimization problem. An EPTAS is simply a fixed-parameter tractable algorithm with respect to this parameter. We offer a number of results concerning the problems Planar TMIN, Planar TMAX and Planar MPSAT defined by Khanna and Motwani: (1) We show that each of these problems of approximation, naturally parameterized by k = 1/ε, is hard for W[1], and thus it is highly unlikely that they admit EPTASs. (One could also interpret this as indicating that PTASs for these problems are unlikely to be a useful way of coping with intractability in the sense of Garey and Johnson.) (2) We show that there are EPTASs for some subproblems described by syntactic restrictions, and establish some limits on how far these positive results can be extended.     

Combined super-/substring and super-/subsequence problems

Super-/substring problems and super-/subsequence problems are well-known problems in stringology that have applications in a variety of areas, such as manufacturing systems design and molecular biology. Here we investigate the complexity of a new type of such problem that forms a combination of a super-/substring and a super-/subsequence problem. Moreover we introduce different types of minimal superstring and maximal substring problems. In particular, we consider the following problems: given a set L of strings and a string S, (i) find a minimal superstring (or maximal substring) of L that is also a supersequence (or a subsequence) of S, (ii) find a minimal supersequence (or maximal subsequence) of L that is also a superstring (or a substring) of S. In addition some non-super-/non-substring and non-super-/non-subsequence variants are studied. We obtain several NP-hardness or even MAX SNP-hardness results and also identify types of “weak minimal” superstrings and “weak maximal” substrings for which (i) is polynomial-time solvable.     

How hard is it to control a group?

We consider group identification models in which the aggregation of individual opinions concerning who is qualified in a given society determines the set of socially qualified persons. In this setting, we study the extent to which social qualification can be changed when societies expand, shrink, or partition themselves. The answers we provide are with respect to the computational complexity of the corresponding control problems and fully cover the class of consent aggregation rules introduced by Samet and Schmeidler (J Econ Theory, 110(2):213–233, 2003) as well as procedural rules for group identification. We obtain both polynomial-time solvability results and NP-hardness results. In addition, we also study these problems from the parameterized complexity perspective, and obtain some fixed-parameter tractability results.     

String-matching with OBDDs

Ordered binary decision diagrams (OBDDs) are a very popular graph representation for Boolean functions. They can be viewed as finite automata recognizing sets of strings of a fixed length, where the letters of the input strings are read at most once in a predefined ordering. The string matching problem with string w as pattern, consists of determining, given an input string, whether or not it contains w as substring. We show that for a fraction of orderings tending to 1 when n increases arbitrarily, the minimal size of an OBDD solving the string matching problem for strings of length n has a growth which is an exponential in n.     

Fixed-Parameter Algorithms for CLOSEST STRING and Related Problems

CLOSEST STRING is one of the core problems in the field of consensus word analysis with particular importance for computational biology. Given k strings of the same length and a nonnegative integer d , find a ``center string' s such that none of the given strings has the Hamming distance greater than d from s . CLOSEST STRING is NP-complete. In biological applications, however, d is usually very small. We show how to solve CLOSEST STRING in linear time for fixed d —the exponential growth in d is bounded by O(d ^d ) . We extend this result to the closely related problems d -MISMATCH and DISTINGUISHING STRING SELECTION. Moreover, we also show that CLOSEST STRING is solvable in linear time when k is fixed and d is arbitrary. In summary, this means that CLOSEST STRING is fixed-parameter tractable with respect to parameter d and with respect to parameter k . Finally, the practical usefulness of our findings is substantiated by some experimental results.     

Sparse LCS Common Substring Alignment

The “Common Substring Alignment” problem is defined as follows. The input consists of a set of strings S₁,S₂…,S_c, with a common substring appearing at least once in each of them, and a target string T. The goal is to compute similarity of all strings S_i with T, without computing the part of the common substring over and over again.In this paper we consider the Common Substring Alignment problem for the LCS (Longest Common Subsequence) similarity metric. Our algorithm gains its efficiency by exploiting the sparsity inherent to the LCS problem. Let Y be the common substring, n be the size of the compared sequences, L_y be the length of the LCS of T and Y, denoted |LCS[T,Y]|, and L be max{|LCS[T,S_i]|}. Our algorithm consists of an O(nL_y) time encoding stage that is executed once per common substring, and an O(L) time alignment stage that is executed once for each appearance of the common substring in each source string. The additional running time depends only on the length of the parts of the strings that are not in any common substring.     

Random Access to Advice Strings and Collapsing Results

We propose a model of computation where a Turing machine is given random access to an advice string. With random access, an advice string of exponential length becomes meaningful for polynomially bounded complexity classes. We compare the power of complexity classes under this model. It gives a more stringent notion than the usual model of computation with relativization. Under this model of random access, we prove that there exist advice strings such that the polynomial-time hierarchy PH and parity polynomial-time ⊕P all collapse to P. Our main proof technique uses the decision tree lower bounds for constant depth circuits [Y], [C], [Ha], and the algebraic machinery of Razborov [R] and Smolensky [S].     

Linear Time Algorithms for Generalizations of the Longest Common Substring Problem

In its simplest form, the longest common substring problem is to find a longest substring common to two or multiple strings. Using (generalized) suffix trees, this problem can be solved in linear time and space. A first generalization is the k -common substring problem: Given m strings of total length n, for all k with 2≤k≤m simultaneously find a longest substring common to at least k of the strings. It is known that the k-common substring problem can also be solved in O(n) time (Hui in Proc. 3rd Annual Symposium on Combinatorial Pattern Matching, volume 644 of Lecture Notes in Computer Science, pp. 230–243, Springer, Berlin, 1992). A further generalization is the k -common repeated substring problem: Given m strings T ⁽¹⁾,T ⁽²⁾,…,T ^(m) of total length n and m positive integers x ₁,…,x _m , for all k with 1≤k≤m simultaneously find a longest string ω for which there are at least k strings \(T^{(i_{1})},T^{(i_{2})},\ldots,T^{(i_{k})}\) (1≤i ₁<i ₂<???<i _k ≤m) such that ω occurs at least \(x_{i_{j}}\) times in \(T^{(i_{j})}\) for each j with 1≤j≤k. (For x ₁=???=x _m =1, we have the k-common substring problem.) In this paper, we present the first O(n) time algorithm for the k-common repeated substring problem. Our solution is based on a new linear time algorithm for the k-common substring problem.     

Constant Thresholds Can Make Target Set Selection Tractable

Target Set Selection, which is a prominent NP-hard problem occurring in social network analysis and distributed computing, is notoriously hard both in terms of achieving useful polynomial-time approximation as well as fixed-parameter algorithms. Given an undirected graph, the task is to select a minimum number of vertices into a “target set” such that all other vertices will become active in the course of a dynamic process (which may go through several activation rounds). A vertex, equipped with a threshold value t, becomes active once at least t of its neighbors are active; initially, only the target set vertices are active. We contribute further insights into the existence of islands of tractability for Target Set Selection by spotting new parameterizations characterizing some sparse graphs as well as some “cliquish” graphs and developing corresponding fixed-parameter tractability and (parameterized) hardness results. In particular, we demonstrate that upper-bounding the thresholds by a constant may significantly alleviate the search for efficiently solvable, but still meaningful special cases of Target Set Selection.     

Substring Range Reporting

We revisit various string indexing problems with range reporting features, namely, position-restricted substring searching, indexing substrings with gaps, and indexing substrings with intervals. We obtain the following main results.

• We give efficient reductions for each of the above problems to a new problem, which we call substring range reporting. Hence, we unify the previous work by showing that we may restrict our attention to a single problem rather than studying each of the above problems individually.
• We show how to solve substring range reporting with optimal query time and little space. Combined with our reductions this leads to significantly improved time-space trade-offs for the above problems. In particular, for each problem we obtain the first solutions with optimal time query and O(nlog ^O(1) n) space, where n is the length of the indexed string.
• We show that our techniques for substring range reporting generalize to substring range counting and substring range emptiness variants. We also obtain non-trivial time-space trade-offs for these problems.

Our bounds for substring range reporting are based on a novel combination of suffix trees and range reporting data structures. The reductions are simple and general and may apply to other combinations of string indexing with range reporting.     

Algorithms for subsequence combinatorics

A subsequence is obtained from a string by deleting any number of characters; thus in contrast to a substring, a subsequence is not necessarily a contiguous part of the string. Counting subsequences under various constraints has become relevant to biological sequence analysis, to machine learning, to coding theory, to the analysis of categorical time series in the social sciences, and to the theory of word complexity. We present theorems that lead to efficient dynamic programming algorithms to count (1) distinct subsequences in a string, (2) distinct common subsequences of two strings, (3) matching joint embeddings in two strings, (4) distinct subsequences with a given minimum span, and (5) sequences generated by a string allowing characters to come in runs of a length that is bounded from above.     

On the longest common parameterized subsequence

The well-known problem of the longest common subsequence (LCS), of two strings of lengths n$n$ and m$m$ respectively, is O(nm)$O\left(nm\right)$-time solvable and is a classical distance measure for strings. Another well-studied string comparison measure is that of parameterized matching, where two equal-length strings are a parameterized match if there exists a bijection on the alphabets such that one string matches the other under the bijection. All works associated with parameterized pattern matching present polynomial time algorithms.     

Efficient algorithms for consensus string problems minimizing both distance sum and radius

The consensus (string) problem is finding a representative string, called a consensus, of a given set S of strings. In this paper we deal with consensus problems considering both distance sum and radius, where the distance sum is the sum of (Hamming) distances from the strings in S to the consensus and the radius is the longest (Hamming) distance from the strings in S to the consensus. Although there have been results considering either distance sum or radius, there have been no results considering both, to the best of our knowledge.We present the first algorithms for two consensus problems considering both distance sum and radius for three strings: one problem is to find an optimal consensus minimizing both distance sum and radius. The other problem is to find a bounded consensus such that the distance sum is at most s and the radius is at most r for given constants s and r. Our algorithms are based on characterization of the lower bounds of distance sum and radius, and thus they solve the problems efficiently. Both algorithms run in linear time.     

There is no EPTAS for two-dimensional knapsack

In the d-dimensional (vector) knapsack problem given is a set of items, each having a d-dimensional size vector and a profit, and a d-dimensional bin. The goal is to select a subset of the items of maximum total profit such that the sum of all vectors is bounded by the bin capacity in each dimension. It is well known that, unless P=NP, there is no fully polynomial-time approximation scheme for d-dimensional knapsack, already for d=2. The best known result is a polynomial-time approximation scheme (PTAS) due to Frieze and Clarke [A.M. Frieze, M. Clarke, Approximation algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses, European J. Operat. Res. 15 (1) (1984) 100-109] for the case where d?2 is some fixed constant. A fundamental open question is whether the problem admits an efficient PTAS (EPTAS).In this paper we resolve this question by showing that there is no EPTAS for d-dimensional knapsack, already for d=2, unless W[1]=FPT. Furthermore, we show that unless all problems in SNP are solvable in sub-exponential time, there is no approximation scheme for two-dimensional knapsack whose running time is , for any function f. Together, the two results suggest that a significant improvement over the running time of the scheme of Frieze and Clarke is unlikely to exist.     

支持局部最优化匹配的近似子串查询算法

基于编辑距离的字符串近似查询算法一般是先给定阈值k,然后计算那些与查询串的编辑距离小于或等于k的结果。但是对于近似子串查询,结果中有很多是交叠的,并且是无意义的,于是提出了一种局部最优化匹配的概念,只计算那些符合阈值条件,并且是局部最优的结果,这样不仅避免了结果的交叠,而且极大节省了时间开销。给出了支持局部最优化匹配的近似子串查询的定义,相应提出了一种基于gram索引的局部最优化近似子串查询算法,分析了子串近似匹配过程中的规律,研究了基于局部最优化匹配的边界限定和过滤策略,给出了一种过滤优化的局部最优化近似子串查询算法,提高了查询效率。     

Fixed-parameter algorithms for Kemeny rankings

The computation of Kemeny rankings is central to many applications in the context of rank aggregation. Given a set of permutations (votes) over a set of candidates, one searches for a “consensus permutation” that is “closest” to the given set of permutations. Unfortunately, the problem is NP-hard. We provide a broad study of the parameterized complexity for computing optimal Kemeny rankings. Besides the three obvious parameters “number of votes”, “number of candidates”, and solution size (called Kemeny score), we consider further structural parameterizations. More specifically, we show that the Kemeny score (and a corresponding Kemeny ranking) of an election can be computed efficiently whenever the average pairwise distance between two input votes is not too large. In other words, Kemeny Score is fixed-parameter tractable with respect to the parameter “average pairwise Kendall–Tau distance _da$d_a$”. We describe a fixed-parameter algorithm with running time 16^⌈_da⌉⋅poly$16^{\lceil d_a\rceil }\cdot poly$. Moreover, we extend our studies to the parameters “maximum range” and “average range” of positions a candidate takes in the input votes. Whereas Kemeny Score remains fixed-parameter tractable with respect to the parameter “maximum range”, it becomes NP-complete in the case of an average range of two. This excludes fixed-parameter tractability with respect to the parameter “average range” unless P=NP. Finally, we extend some of our results to votes with ties and incomplete votes, where in both cases one no longer has permutations as input.     

两种基于双向比较的最长公共子串算法

查找两个给定字符串的最长公共子串(LCSstr)是一类重要字符串分析问题,在字符串近似匹配、计算机病毒特征码对比等方面有着广泛的用途.最长公共子串算法目前主要包括动态规划算法(LCSstrDP)和后缀数组算法(LCSstrSA),分别用于短串和长串的最长公共子串计算.前者代码简洁,但计算速度较慢,后者速度很快但算法非常复杂.提出两种基于双向比较的最长公共子串算法,即LCSstrSeL和LCSstrSCeL.LCSstrSeL跨越已有的最长公共子串长度,与LCSstrDP相比,代码同样简洁,平均计算效率提高近一个数量级,并且不需要额外的存储空间.LCSstrSCeL是在LCSstrSeL的基础上,增加字符跨越、连续同值区间跨越等机制,平均效率较LCSstrSeL亦有一定程度的提高,内存开销与LCSstrDP相近,在中小长度的字符串LCSstr计算中,平均计算效率高于LCSstrSA,某些情况下的计算效率可达到亚线性的速度.     

一种基于独立性统计的子串归并算法

现行的子串归并算法都是采用一对一的方式针对同频子串提出的。但是在使用词法分析工具对文本进行切分时,不可避免地会产生很多的分词碎片,这直接导致了很多无意义子串的产生。通过分析这些无意义子串和众多父串之间的这种一对多关系,提出了一种基于独立性统计的子串归并算法。最后将该子串归并算法应用在中文术语抽取系统中,使得系统的准确率从91.3%提升到了93.32%。     

隐私保护DNA序列汉明距离计算问题

DNA序列承载着人体重要的生物学信息，如何在保护隐私的情况下正确地对不同的DNA序列进行比对，成为亟待研究的科学问题。汉明距离在一定程度上刻画了两个DNA序列的相似程度，在保护隐私的情况下，研究DNA序列的汉明距离计算问题。首先定义了DNA序列的0-1编码规则，该规则将长度为n的DNA序列编码成长度为4n的0-1串，证明了两个DNA序列的汉明距离等于它们的0-1编码串的汉明距离的一半。以此结论为基础，以GM加密算法为主要密码学工具，构造了计算DNA序列汉明距离的一个安全两方计算协议。在半诚实攻击者模型下，证明了协议的正确性，给出了基于模拟器的安全性证明，并对协议的效率进行了分析。     

Communication-Aware Processor Allocation for Supercomputers: Finding Point Sets of Small Average Distance

We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of communication hops. The associated clustering problem is as follows: Given n points in ℜ ^d , find a size-k subset with minimum average pairwise L ₁ distance. We present a natural approximation algorithm and show that it is a -approximation for two-dimensional grids; in d dimensions, the approximation guarantee is , which is tight. We also give a polynomial-time approximation scheme (PTAS) for constant dimension d, and we report on experimental results.