38436825
Fixed-Parameter Approximation: Conceptual Framework and Approximability Results
The notion of fixed-parameter approximation is introduced to investigate the approximability of optimization problems within the framework of fixed-parameter computation. This work partially aims at enhancing the world of fixed-parameter computation in parallel with the conventional theory of computation that includes both exact and approximate computations. In particular, it is proved that fixed-parameter approximability is closely related to the approximation of small-cost solutions in polynomial time. It is also demonstrated that many fixed-parameter intractable problems are not fixed-parameter approximable. On the other hand, fixed-parameter approximation appears to be a viable approach to solving some inapproximable yet important optimization problems. For instance, all problems in the class MAX SNP admit fixed-parameter approximation schemes in time O(2$^{O((1-{\epsilon}/{\it O}(1)){\it k})}$p(n)) for any small e> 0.
2661456
Linear FPT reductions and computational lower bounds
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/ε)no(1/ε) for any function f unless an unlikely collapse occurs in parameterized complexity theory.
10668543
Parameterized Computation of LCS for Two Sequences
The problem of finding the longest common subsequence is a well-known optimization problem because of its applications, especially in bioinformatics. In this paper, by applying the techniques developed in parameterized computation, an efficient approach for the problem of finding the longest common subsequence of two sequences is presented. The parameterized approach is compared with the well-known dynamic programming approach for the problem. The parameterized approach is much more efficient, as is shown by the experimental results.
43590220
Lower Bounds and Parameterized Approach for Longest Common Subsequence
In this paper, different parameterized versions of the longest common subsequence (LCS) problem are extensively investigated and computational lower bound results are derived based on current research progress in parameterized computation. For example, with the number of sequences as the parameter k, the problem is unlikely to be solvable in time f(k)no(k), where n is the length of each sequence and f is any recursive function. The lower bound result is asymptotically tight in consideration of the dynamic programming approach of time O(nk). Computational lower bounds for polynomial-time approximation schemes (PTAS) for the LCS problem are also derived. It is shown that the LCS problem has no PTAS of time f(1/ e)no(1/ e) for any recursive function f, unless all SNP problems are solvable in subexponential time. Compared with former results on this problem, this result has its significance. Finally a parameterized approach for the LCS problem is discussed, which is more efficient than the dynamic programming approach, especially when applied to large scale sequences.
15675165
Maximum Common Subgraph: Upper Bound and Lower Bound Results
In bio informatics, the biological structure matching problems can be formulated as the problem of finding the maximum common subgraph. Among the many different variants of the maximum common subgraph problem, the maximum common induced subgraph of two graphs is of special interest. In this paper, first we derive the lower bound result for the exact algorithms of the maximum common induced subgraph of two graphs, based on the current research progress in the area of parameterized computation. Then we investigate the upper bound and design the approaches for addressing this problem. Basically, this problem can be reduced to find a maximum clique in the product graph of the two given graphs. In consideration of the upper bound result, the obtained lower bound result is asymptotically tight. We would like to point out that our lower bound result presented here is currently best-known
2218327
Strong computational lower bounds via parameterized complexity
We develop new techniques for deriving strong computational lower bounds for a class of well-known NP-hard problems. This class includes weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(n^k) 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)n^o^(^k^) for any function f, even if we restrict the parameter values 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 of the order @Q(@m(n)) for any reasonable function @m, no algorithm of running time n^o^(^k^) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds on the computational complexity are also derived for other NP-hard problems in the above class. Our techniques can be further extended to derive computational lower bounds on polynomial time approximation schemes 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)n^o^(^1^/^@e^) for any function f unless an unlikely collapse occurs in parameterized complexity theory.
8009887
A Framework of Filtering, Clustering and Dynamic Layout Graphs for Visualization
Many classical graph visualization algorithms have already been developed over the past decades. However, these algorithms face difficulties in practice, such as the overlapping node problem, large graph layout and dynamic graph layout. In order to solve these problems, this paper aims to systematically address algorithmic issues related to a novel framework that describes the process of graph visualization applications. First of all, a framework for graph visualization is described. As the important parts of this framework, we then develop two effective algorithms for filtering and clustering large graphs for the layouts. As for the dynamic graph layout, a new approach to removing overlapping nodes called force-transfer algorithm is developed. The framework has been implemented in a prototype called PGA to demonstrate the performance of the proposed algorithms. Finally, a case study is provided.
27390518
Session Boundary Detection for Association Rule Learning Using n-Gram Language Models
We present a statistical method using n-gram language models to identify session boundaries in a large collection of Livelink log data. The identified sessions are then used for association rule learning. Unlike the traditional ad hoc timeout method, which uses fixed time thresholds for session identification, our method uses an information theoretic approach that provides a natural technique for performing dynamic session identification. The effectiveness of our approach is evaluated with respect to 4 different interestingness measures. We find that we obtain a significant improvement in each interestingness measure, ranging from a 26.6% to 39% improvement on average over the best results obtained with standard timeout methods.
2071657
Comparison of interestingness functions for learning web usage patterns
Livelink is a collaborative intranet, extranet and e-business application that enables employees and business partners of an organization to capture, share and reuse business information and knowledge. The usage of the Livelink software has been recorded by the Livelink Web server in its log files. We present an application of data mining techniques to the Livelink Web usage data. In particular, we focus on how to find interesting association rules and sequential patterns from the Livelink log files. A number of interestingness measures are used in our application to identify interesting rules and patterns. We present a comparison of these measures based on the feedback from domain experts. Some of the interestingness measures are found to be better than others.
7754676
FDUQA on TREC2003 QA task
It is the fourth time that we take part in the QA track. Our system, FDUQA, is based on our previous system (Wu et al, 2002). FDUQA includes an offline part and an online part. We make great efforts on the online part while leaving the offline part unchanged. We have tried many natural language processing techniques, and incorporated many sources of world knowledge, including Web. A novel Query formulation technique has also been put forward. In addition, we’ve tried another attempt on answer extraction in this year’s task. In the second section, we will describe the architecture of our QA system; and give a detailed description on the Query formulation for Web search in the third section; while in the fourth section, we will introduce our new attempt on answer extraction; and we will present our performance in the last section.
13555130
Deformable-Model Based Textured Object Segmentation
In this paper, we present a deformable-model based solution for segmenting objects with complex texture patterns of all scales. The external image forces in traditional deformable models come primarily from edges or gradient information and it becomes problematic when the object surfaces have complex large-scale texture patterns that generate many local edges within a same region. We introduce a new textured object segmentation algorithm that has both the robustness of model-based approaches and the ability to deal with non-uniform textures of both small and large scales. The main contributions include an information-theoretical approach for computing the natural scale of a “texon” based on model-interior texture, a nonparametric texture statistics comparison technique and the determination of object belongingness through belief propagation. Another important property of the proposed algorithm is in that the texture statistics of an object of interest are learned online from evolving model interiors, requiring no other a priori information. We demonstrate the potential of this model-based framework for texture learning and segmentation using both natural and medical images with various textures of all scales and patterns.