No label defined (Q3341929)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3876623
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3876623 |
Statements
1983
0 references
approximate algorithms
0 references
probabilistic models
0 references
algorithms for data base scheme design
0 references
largest Berge acyclic subscheme
0 references
random hypergraphs
0 references
0.7942012548446655
0 references
0.7638512253761292
0 references
0.7525895833969116
0 references
[For the entire collection see Zbl 0527.00033.] Hypergraphs are a widely used mathematical model for formalizing data base schemes in the relational model and describing algorithms for data base scheme design and manipulation. In the paper the problem of determining the largest Berge acyclic subscheme of a data base scheme is examined evaluating both the optimal solution and the approximate solution given by a greedy heuristic with respect to two different models of random hypergraphs. The first model is an extension of the constant density model for random graphs. The second model is more strictly related to data base applications. In this case, fixed a constant p between 0 and 1, a random hypergraph of n nodes is a hypergraph in which, given any two nodes n and m, the probability that n and m belong to the same hyperedge is equal to p independently from the fact that n and m belong to any other hyperedge. In the first model it is shown that the ratio between the values of the optimal and approximate solution is bounded by \(k^{1/(k-1)}\) almost surely, while in the second model the ratio is bounded by 2 almost surely.
0 references