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: Goto entry point

 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:

 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},
}