MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
Downloading URL:
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:
Note, Abstract, ©
(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},
 ADDRESS = {Rome, Italy},
 MONTH = {September},
}

Entry last modified by Christine Kiesel, 07/15/2014
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]		Created
02/22/2005 07:41:53 PM
Revisions
2.
1.
0.

Editor(s)
Christine Kiesel
Christine Kiesel
Khaled Elbassioni

Edit Dates
02.05.2007 16:47:44
02.06.2006 15:17:32
02/22/2005 07:41:53 PM

File Attachment Icon
ESA02.pdf