MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Boros, Endre
Elbassioni, Khaled M.
Gurvich, Vladimir
Khachiyan, Leonid		dblp
dblp
dblp
dblp
Not MPG Author(s):
Boros, Endre
Gurvich, Vladimir
Khachiyan, Leonid
Editor(s):
Ribeiro, Celso C.
Martins, Simone L.		dblp
dblp
Not MPII Editor(s):
Ribeiro, Celso C.
Martins, Simone L.
BibTeX cite key*:
Elbassioni2004a
Title, Booktitle
Title*:
An Efficient Implementation of a Joint Generation Algorithm
WAE04.pdf (264.95 KB)
Booktitle*:
Experimental and efficient algorithms : Third International Workshop, WEA 2004
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Angra dos Reis, Brazil
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
25 May 2004
Event End Date:
28 May 2004
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
3059
Number:
Month:
May
Pages:
114-128
Year*:
2004
VG Wort Pages:
ISBN/ISSN:
3-540-22067-4
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Let $\cC$ be an n-dimensional integral box, and $\pi$ be a monotone property defined over the elements of $\cC$. We consider the problems of incrementally generating jointly the families $\cF_{\pi}$ and $\cI(cF_{\pi})$ of all minimal subsets satisfying property $\pi$ and all maximal subsets not satisfying property $\pi$, when $\pi$ is given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time. In this paper, we present an efficient implementation of this procedure. We present experimental results to evaluate our implementation for a number of interesting monotone properties $\pi$.
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{Elbassioni2004a,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Gurvich, Vladimir and Khachiyan, Leonid},
 EDITOR = {Ribeiro, Celso C. and Martins, Simone L.},
 TITLE = {An Efficient Implementation of a Joint Generation Algorithm},
 BOOKTITLE = {Experimental and efficient algorithms : Third International Workshop, WEA 2004},
 PUBLISHER = {Springer},
 YEAR = {2004},
 VOLUME = {3059},
 PAGES = {114--128},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Angra dos Reis, Brazil},
 MONTH = {May},
 ISBN = {3-540-22067-4},
}

Entry last modified by Christine Kiesel, 05/02/2007
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)
Khaled Elbassioni		Created
02/22/2005 08:18:24 PM
Revisions
5.
4.
3.
2.
1.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
02.05.2007 15:39:46
21.04.2005 16:13:06
21.04.2005 16:00:38
21.04.2005 15:59:53
21.04.2005 15:58:58

File Attachment Icon
WAE04.pdf