Approximating coloring and maximum independent sets in 3-uniform hypergraphs (Q2768313)

In this 2-page note the authors propose approximation algorithms for coloring and independent set problems in 3-uniform hypergraphs. First, they discuss an algorithm for finding a large independent set in an \(n\)-vertex hypergraph with independent set of size \(\geq\gamma n\), for a constant \(\gamma> 0\). Then they use this algorithm as a subroutine of an algorithm for coloring 3-uniform 2-colorable hypergraphs in \(\widetilde O(n^{1/5})\) colors, thus improving the best currently known \(\widetilde O(n^{9/41})\) algorithm. Finally, they show how to improve these algorithms using the local ratio approach. Due to space limits they present only brief outlines of their results.NEWLINENEWLINEFor the entire collection see [Zbl 0972.00057].