Deutsch

Benutzerhandbuch Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

#### An Efficient Implementation of a Joint Generation Algorithm

##### MPG-Autoren
/persons/resource/persons44374

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

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

Boros, E., Elbassioni, K., Gurvich, V., & Khachiyan, L. (2004). An Efficient Implementation of a Joint Generation Algorithm. In Experimental and efficient algorithms: Third International Workshop, WEA 2004 (pp. 114-128). Berlin, Germany: Springer.

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$.