Electronic Journal Article
@Article
Zeitschriftenartikel in einem e-Journal



Show entries of:

this year (2014) | last year (2013) | two years ago (2012) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Boros, Endre
Elbassioni, Khaled M.
Khachiyan, Leonid
Gurvich, Vladimir

dblp
dblp
dblp
dblp

Not MPG Author(s):

Boros, Endre
Gurvich, Vladimir
Khachiyan, Leonid

BibTeX cite key*:

Elbassioni2002b

Title

Title*:

Generating Dual-Bounded Hypergraphs


oms.ps (318.42 KB)

Journal

Journal Title*:

Optimization Methods and Software

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Taylor & Francis

Publisher's URL:


Publisher's
Address:


ISSN:


Vol, No, Year, pp.

Volume:

17

Number:

5

Month:


Year*:

2002

Pages:

33

Number of VG Pages:


Sequence Number:


DOI:


Abstract, Links, (C)

Note:


(LaTeX) Abstract:

This paper surveys some recent results on the generation of
implicitly given hypergraphs and their applications in Boolean and integer programming, data mining, reliability theory, and
combinatorics.

Given a monotone property $\pi$ over the
subsets of a finite set $V$, we consider the problem of
incrementally generating the family $\cF_{\pi}$ of all
minimal subsets satisfying property $\pi$, when
$\pi$ is given by a polynomial-time satisfiability oracle.
For a number of interesting monotone properties, the family $\cF_{\pi}$ turns out to be {\em uniformly dual-bounded}, allowing for the incrementally efficient enumeration of the members of $\cF_{\pi}$.

Important applications include the efficient generation of minimal infrequent sets of a database (data mining), minimal connectivity ensuring collections of subgraphs from a given list (reliability theory), minimal feasible solutions to a system of monotone inequalities in integer variables (integer programming), minimal spanning collections of subspaces from a given list (linear algebra) and maximal independent sets in the intersection of matroids (combinatorial optimization).
In contrast to these results, the analogous problem of generating
the family of all maximal subsets not having property $\pi$
is NP-hard for almost all applications mentioned above.

URL for the Abstract:


Categories / Keywords:

Hypergraph, Independent set, Transversal, Matroid, Polymatroid, Monotone Boolean function, Integer programming, Data mining, Maximal frequent set, Enumeration, Incremental polynomial time

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


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:

@MISC{Elbassioni2002b,
AUTHOR = {Boros, Endre and Elbassioni, Khaled M. and Khachiyan, Leonid and Gurvich, Vladimir},
TITLE = {Generating Dual-Bounded Hypergraphs},
JOURNAL = {Optimization Methods and Software},
PUBLISHER = {Taylor & Francis},
YEAR = {2002},
NUMBER = {5},
VOLUME = {17},
PAGES = {33},
}


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 Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
oms.ps