Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
WAE04.pdf