Approximating coloring and maximum independent sets in 3-uniform hypergraphs
Michael Krivelevich, Ram Nathaniel, Benny Sudakov · 2001
We discuss approximation algorithms for the coloring problem and the maximum independent set problem in 3-uniform hypergraphs. An algorithm for coloring 3-uniform 2-colorable hypergraphs in ~ O(n 1=5 ) colors is presented, improving previously known results. Also, for every fixed > 1=2, we describe an algorithm that, given a 3-uniform hypergraph H on n vertices with an independent set of size n, nds an independent set of size ~ 310 (n; n 6 3 ). 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.