We present a complete classification of the distributed computational complexity of local optimization problems in directed cycles, both in the deterministic and in the randomized LOCAL model.

We show that for any local optimization problem $\Pi$—which may be a min-sum, max-sum, min-max, or max-min problem for any local cost or utility function over a finite alphabet—and for any constant approximation ratio $\alpha$, the task of finding an $\alpha$-approximation of $\Pi$ in directed cycles has one of the following four complexity profiles:

1. $O(1)$ rounds in deterministic LOCAL and $O(1)$ rounds in randomized LOCAL,
2. $\Theta(\log^* n)$ rounds in deterministic LOCAL and $O(1)$ rounds in randomized LOCAL,
3. $\Theta(\log^* n)$ rounds in deterministic LOCAL and $\Theta(\log^* n)$ rounds in randomized LOCAL, or
4. $\Theta(n)$ rounds in deterministic LOCAL and $\Theta(n)$ rounds in randomized LOCAL.

Moreover, for any given $\Pi$ and $\alpha$, we can determine the complexity class automatically with an efficient centralized meta-algorithm, and we can also synthesize an asymptotically optimal distributed algorithm.

Before this work, analogous results were known only for local search problems, such as locally checkable labeling problems. Local optimization problems strictly generalize local search problems and include many commonly studied distributed tasks, including approximations of maximum independent set, minimum vertex cover, minimum dominating set, and minimum vertex coloring.