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

      0 references
      0 references
      0 references
      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
      [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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references