English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

An Algorithm for Dualization in Products of Lattices and Its Applications

MPS-Authors
/persons/resource/persons44374

Elbassioni,  Khaled M.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Elbassioni, K. M. (2002). An Algorithm for Dualization in Products of Lattices and Its Applications. In Algorithms - ESA 2002 (pp. 424-435). Berlin: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0019-ED47-D
Abstract
Let \cL=\cL_1×⋅s×\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.