Catálogo de publicaciones - libros

A core problem in data mining is enumerating frequently-occurring itemsets in a given set of transactions. The search and enumeration versions of this problem have recently been proven NP - and # P -hard, respectively (Gunopulos et al , 2003) and known algorithms all have running times whose exponential terms are functions of either the size of the largest transaction in the input and/or the largest itemset in the output. In this paper, we analyze the complexity of the size- k frequent itemset enumeration problem relative to a variety of parameterizations. Many of our hardness results are proved using a recent extension of parameterized complexity to solution-counting problems (McCartin, 2002). These results include hardness for versions of this problem based on restricted transaction-set structure. We also derive a collection of fixed-parameter algorithms using off-the-shelf parameterized algorithm design techniques, several of which suggest new algorithmic directions for the frequent itemset enumeration problem.

We develop a new randomized method, random separation , for solving fixed-cardinality optimization problems on graphs, i.e., problems concerning solutions with exactly a fixed number k of elements (e.g., k vertices V ′) that optimize solution values (e.g., the number of edges covered by V ′). The key idea of the method is to partition the vertex set of a graph randomly into two disjoint sets to separate a solution from the rest of the graph into connected components, and then select appropriate components to form a solution. We can use universal sets to derandomize algorithms obtained from this method. This new method is versatile and powerful as it can be used to solve a wide range of fixed-cardinality optimization problems for degree-bounded graphs, graphs of bounded degeneracy (a large family of graphs that contains degree-bounded graphs, planar graphs, graphs of bounded tree-width, and nontrivial minor-closed families of graphs), and even general graphs.

A survey is given of the main techniques in parameterized algorithm design, with a focus on formal descriptions of the less familiar techniques. A taxonomy of techniques is proposed, under the four main headings of Branching, Kernelization, Induction and Win/Win. In this classification the Extremal Method is viewed as the natural maximization counterpart of Iterative Compression, under the heading of Induction. The formal description given of Greedy Localization generalizes the application of this technique to a larger class of problems.

The notion of a “problem kernel” plays a central role in the design of fixed-parameter algorithms. The $\mathcal{FPT}$ literature is rich in kernelization algorithms that exhibit fundamentally different approaches. We highlight these differences and discuss several generalizations and restrictions of the standard notion.

One of the main objectives of the talk is to survey the history of the practical algorithmic strategy of preprocessing (also called data-reduction and kernelization ) since the beginnings of computer science, and to overview what theoretical computer science has been able to say about it.

When dealing with hard computational problems (NP-complete or worse), Scientists, Engineers and other users of software provided by Computer Scientists care most about how large a problem instance a particular method is able to solve in reasonable time. In this talk, we discuss the contributions and deficiencies of current fixed parameter tractability methods within this context.