✦ LIBER ✦

Approximate Set Covering in Uniform Hypergraphs

✍ Scribed by Michael Krivelevich

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 296 KB
Volume: 25
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1997.0872

No coin nor oath required. For personal study only.

✦ Synopsis

The weighted set covering problem, restricted to the class of r-uniform hypergraphs, is considered. We propose a new approach, based on a recent result of Aharoni, Holzman, and Krivelevich about the ratio of integer and fractional covering numbers in k-colorable r-uniform hypergraphs. This approach, applied to hypergraphs of maximal degree bounded by ⌬, yields an algorithm with approxima-Ž 1r Ž ry1. . tion ratio r 1 y cr⌬ . Next, we combine this approach with an adaptation of the local ratio theorem of Bar-Yehuda and Even for hypergraphs and present a general framework of approximation algorithms, based on subhypergraph exclusion. An application of this scheme is described, providing an algorithm with Ž Ž ry1.r r . approximation ratio r 1 y crn for hypergraphs on n vertices. We discuss also the limitations of this approach.

📜 SIMILAR VOLUMES

Covering Non-uniform Hypergraphs

✍ Endre Boros; Yair Caro; Zoltán Füredi; Raphael Yuster 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 160 KB

A subset of the vertices in a hypergraph is a cover if it intersects every edge. Let {(H) denote the cardinality of a minimum cover in the hypergraph H, and let us denote by g(n) the maximum of {(H) taken over all hypergraphs H with n vertices and with no two hyperedges of the same size. We show tha

Approximating Coloring and Maximum Indep

Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs

✍ Michael Krivelevich; Ram Nathaniel; Benny Sudakov 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 120 KB

We discuss approximation algorithms for the coloring problem and the maximum independent set problem in 3-uniform hypergraphs. An algorithm for coloring ˜1r5 Ž . ## 3-uniform 2-colorable hypergraphs in O n colors is presented, improving previously known results. Also, for every fixed ␥ ) 1r2, we

Uniform rational approximation on large

Uniform rational approximation on large data sets

✍ E. H. Kaufman Jr.; S. F. McCormick; G. D. Taylor 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 476 KB

Best Uniform Convex Approximation on a C

Best Uniform Convex Approximation on a Compact Convex Set

✍ J.T. Chan 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 183 KB

Uniform Lipschitz Continuity of Bestlp-A

Uniform Lipschitz Continuity of Bestlp-Approximations by Polyhedral Sets

✍ Martina Finzel; Wu Li 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 70 KB

Singular coverings and non-uniform notio

Singular coverings and non-uniform notions of closed set computability

✍ Stéphane Le Roux; Martin Ziegler 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 250 KB

## Abstract The empty set of course contains no computable point. On the other hand, surprising results due to Zaslavskiĭ, Tseĭtin, Kreisel, and Lacombe have asserted the existence of non‐empty co‐r. e. closed sets devoid of computable points: sets which are even “large” in the sense of positive Le