Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop

 Show entries of: this year (2020) | last year (2019) | two years ago (2018) | Notes URL
 Action: login to update Options: Library locked Goto entry point

 Author, Editor
 Author(s): Elbassioni, Khaled M. dblp
 Editor(s): Not MPII Editor(s): Rolf H. Möhring, Rajeev Raman
 BibTeX cite key*: Elbassioni2002d

 Title, Booktitle
 Title*: An Algorithm for Dualization in Products of Lattices and Its Applications ESA02.pdf (223.52 KB) Booktitle*: Algorithms - ESA 2002, 10th Annual European Symposium

 Event, URLs
 URL of the conference: URL for downloading the paper: Event Address*: Rome, Italy Language: English Event Date* (no longer used): Organization: Event Start Date: 17 September 2002 Event End Date: 21 September 2002

 Publisher
 Name*: Springer URL: Address*: Berlin, Germany Type:

 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 2461 Number: Month: September Pages: 424-435 Year*: 2002 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:

 (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

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Elbassioni2002d,
AUTHOR = {Elbassioni, Khaled M.},
TITLE = {An Algorithm for Dualization in Products of Lattices and Its Applications},
BOOKTITLE = {Algorithms - ESA 2002, 10th Annual European Symposium},
PUBLISHER = {Springer},
YEAR = {2002},
VOLUME = {2461},
PAGES = {424--435},
SERIES = {Lecture Notes in Computer Science},