✦ LIBER ✦

Approximating Coloring and Maximum Independent Sets in 3-Uniform Hypergraphs

✍ Scribed by Michael Krivelevich; Ram Nathaniel; Benny Sudakov

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 120 KB
Volume: 41
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2001.1173

No coin nor oath required. For personal study only.

✦ Synopsis

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 describe an algorithm that, given a 3-uniform hypergraph H on n vertices with an independent set of size ˜6␥y3 Ž Ž .. ␥ n, finds an independent set of size ⍀ min n, n

. For certain values of ␥ we are able to improve this using the local ratio approach. The results are obtained through semidefinite programming relaxations of these optimization problems. ᮊ

📜 SIMILAR VOLUMES

Very rapidly mixing Markov chains for 2Δ

Very rapidly mixing Markov chains for 2Δ-colorings and for independent sets in a graph with maximum degree 4

✍ Michael Molloy 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 140 KB 👁 1 views

We introduce a new technique for analyzing the mixing rate of Markov chains. We use it to prove that the Glauber dynamics on 2 -colorings of a graph with maximum degree mixes in O n log n time. We prove the same mixing rate for the Insert/Delete/Drag chain of Dyer and Greenhill (Random Structures A