 |
|
(LaTeX) Abstract: |
Let $\cL=\cL_1\times\cdots\times\cL_n$ be the product of $n$
lattices, each of which has a bounded width. Given a subset
$\cA\subseteq\cL$, we show that the problem of extending a given partial list of maximal independent elements of $\cA$ in $\cL$ can be solved in quasi-polynomial time.
This result implies, in particular, that the problem of generating all minimal infrequent elements for a database with semi-lattice attributes, and the problem of generating
all maximal boxes that contain at most a specified number of points from a given $n$-dimensional point set, can both be solved in incremental quasi-polynomial time. |
Keywords: |
Boxes, data mining, dualization, incremental generation algorithms, lattice, polymatroid functions, poset, points, systems of inequalities, quasi-polynomial. |
|
|
|
|
Download
Access Level: |
Public |
|