18922506
Parameterized Complexity of Generalized Vertex Cover Problems
Important generalizations of the Vertex Cover problem (Connected Vertex Cover, Capacitated Vertex Cover, and Maximum Partial Vertex Cover) have been intensively studied in terms of approximability. However, their parameterized complexity has so far been completely open. We close this gap here by showing that, with the size of the desired vertex cover as parameter, Connected Vertex Cover and Capacitated Vertex Cover are both fixed-parameter tractable while Maximum Partial Vertex Cover is W[1]-hard. This answers two open questions from the literature. The results extend to several closely related problems. Interestingly, although the considered generalized Vertex Cover problems behave very similar in terms of constant-factor approximability, they display a wide range of different characteristics when investigating their parameterized complexities.
1715544
Pattern matching for arc-annotated sequences
We study pattern matching for arc-annotated sequences. An O(nm) time algorithm is given for the problem to determine whether a length m sequence with nested arc annotation is an arc-preserving subsequence (aps) of a length n sequence with nested arc annotation, called APS(NESTED,NESTED). Arc-annotated sequences and, in particular, those with nested arc annotation are motivated by applications in RNA structure comparison. Our algorithm generalizes results for ordered tree inclusion problems and it is useful for recent fixed-parameter algorithms for LAPCS(NESTED,NESTED), which is the problem of computing a longest arc-preserving common subsequence of two sequences with nested arc annotations. In particular, the presented dynamic programming methodology implies a quadratic-time algorithm for an open problem posed by Vialette.
14425036
Parameterized Intractability of Distinguishing Substring Selection
Abstract
A central question in computational biology is the design of genetic
markers to distinguish between two given sets of (DNA) sequences. This question is formalized as 
the NP-complete Distinguishing Substring Selection problem (DSSS for short) which asks, given a set of "good" strings and a set of "bad" strings, for a solution string which is, with respect to the Hamming metric, "away" from the good strings and "close" to the bad strings. More precisely, given integers dg, db, and L, we ask for a length-L string s such that s has Hamming distance at least dg to every length-L substring of the good strings and such that every bad string has a length-L substring with Hamming distance at most db to s. Studying the parameterized complexity of DSSS, we show that, already for binary alphabet, DSSS is W[1]-hard with respect to its natural parameters. This, in particular, implies that a recently given polynomial-time approximation scheme (PTAS) by Deng et al. cannot be replaced by a so-called efficient polynomial-time approximation scheme (EPTAS) unless an unlikely collapse in parameterized complexity theory occurs. This is seemingly the first computational biology problem for which such a border between PTAS (which exists) and EPTAS (which is unlikely to exist) could be established. By way of contrast, for a special case of DSSS, we present an exact fixed-parameter algorithm solving the problem efficiently. In this way we also exhibit a sharp border between fixed-parameter tractability and intractability results.

14944633
On Exact and Approximation Algorithms for Distinguishing Substring Selection
The NP-complete Distinguishing Substring Selection problem (DSSS for short) asks, given a set of “good” strings and a set of “bad” strings, for a solution string which is, with respect to Hamming metric, “away” from the good strings and “close” to the bad strings.
6020472
Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
We show that the NP-complete Feedback Vertex Set problem, which asks for the smallest set of vertices to remove from a graph to destroy all cycles, is deterministically solvable in O(c^[email protected]?m) time. Here, m denotes the number of graph edges, k denotes the size of the feedback vertex set searched for, and c is a constant. We extend this to an algorithm enumerating all solutions in O(d^[email protected]?m) time for a (larger) constant d. As a further result, we present a fixed-parameter algorithm with runtime O(2^[email protected]?m^2) for the NP-complete Edge Bipartization problem, which asks for at most k edges to remove from a graph to make it bipartite.
9767043
The Computational Complexity of Avoiding Forbidden Submatrices by Row Deletions
We initiate a systematic study of the ROW DELETION(B) problem on matrices: Given an input matrix A and a fixed "forbidden submatrix" B, the task is to remove a minimum number of rows from A such that no row or column permutation of B occurs as a submatrix in the resulting matrix. An application of this problem can be found, for instance, in the construction of perfect phylogenies. Establishing a strong connection to variants of the NP-complete HITTING SET problem, we describe and analyze structural properties of B that make ROW DELETION(B)NP-complete. On the positive side, the close relation with HITTING SET problems yields constant-factor polynomial-time approximation algorithms and fixed-parameter tractability results.
5572698
Concept exchange: constructing interoperable electronic product catalogues in an emergent environment
Research in interoperability of electronic product catalogues has primarily focused on resolving semantic conflicts arisen from the heterogeneously designed electronic product catalogues. We argue that while existing integration strategies providing static connections between various heterogeneous catalogues over mediating ontologies, ontologies themselves exhibit heterogeneity and lack of evolvability. What's more, reclassifying terms to link public ontologies is very difficult to avoid inaccuracy problem that is critical to electronic commerce. This paper highlights the problems of flexibility, exactness and evolvability that have received little attention in the literature and provides an overview of the concept exchange approach to interoperability. It illustrates why this is able to better solve the identified problems, presents the different features compared with other approaches and suggests how the concept exchange framework is working.
37890888
Alibaba International: Building a Global Electronic Marketplace
Alibaba is the largest global electronic marketplace (GEM) in the world in terms of its participated users. It was successful due to the factors of China's foreign trade regime, the image of low product cost of China, Alibaba's contingent adaptation to users' changing requirements and e-commerce environments. Alibaba is not a technically mature GEM platform compared with the ideal functions of GEM. Suggested solution for Alibaba to continuing its success is to adopt a novel GEM connectivity model
18367158
A distributed database server for continuous media
In our project, we are adopting a new approach for handling video data. We view the video as a well-defined data type with its own description, parameters and applicable methods. The system is based on PREDATOR, an open-source object-relational DBMS. PREDATOR uses Shore as the underlying storage manager. Supporting video operations (storing, searching-by-content and streaming) and new query types (query-by-example and multi-feature similarity searching) requires major changes in many of the traditional system components. More specifically, the storage and buffer manager has to deal with huge volumes of data with real-time constraints. Query processing has to consider the video methods and operators in generating, optimizing and executing the query plans.
9204785
Achieving Transparent Integration of Information, Documents and Processes
While progress is made in the individual integration of business information, documents and processes, the issue of how to vertically integrate these individually integrated results needs to be resolved. This paper proposes a novel TRANSCODE approach to the issue. The approach represents business information, business documents and business processes in three TRANSCODE structures, which are then implemented, conceptualized and reified in an integrated and flexible 3-layer TRANSCODE model
6234679
A Model-based Approach to Hair Region Segmentation
Hair regions represent an important external feature in many tasks involving the processing of human faces. Currently, the task of locating the hair region in a facial image requires manual intervention. In this paper we examine the different aspects of the hair region segmentation problem and develop an automatic system for such a problem. The system incorporates the human knowledge on where the hair is usually located in a facial image. Segmentation is performed via the classification of image pixels and is based on both textural and geometrical features. Experiments have shown that the segmentation results are generally satisfactory and are at least comparable to the performance of manual extraction.