  We introduce a lower bounding technique for the min max correlation
clustering problem and, based on this technique, a combinatorial
4-approximation algorithm for complete graphs. This improves upon the previous
best known approximation guarantees of 5, using a linear program formulation
(Kalhan et al., 2019), and 40, for a combinatorial algorithm (Davies et al.,
2023a). We extend this algorithm by a greedy joining heuristic and show
empirically that it improves the state of the art in solution quality and
runtime on several benchmark datasets.
