Partitioning problems in dense hypergraphs
We study the general partitioning problem and the discrepancy problem in dense hypergraphs. Using the regularity lemma (Szemerdi, Problemes Combinatories et Theorie des Graphes (1978), pp. 399402) and its algorithmic version proved in Czygrinow and Rdl (SIAM J. Comput., to appear), we give polynomial-time approximation schemes for the general partitioning problem and for the discrepancy problem.
partitioning problem the regularity lemma approximation algorithm