Summary: Given a hypergraph and a set of colors, we want to find a vertex coloring to minimize the size of any monochromatic set in an edge. We give a deterministic polynomial time approximation algorithm with performance close to the best bound guaranteed by an existential argument. This can be applied to support divide and conquer approaches to various problems. We give two examples. For deterministic DNF approximate counting, this helps us explore the importance of a previously ignored parameter, the maximum number of appearances of any variable, and we construct algorithms that are particularly good when this parameter is small. For partially ordered sets, we are able to constructivize the dimension bound given by {\it Z. Füredi} and {\it J. Kahn} [Order 3, 15‒20 (1986; Zbl 0656.06005)].