We consider the Minimum Linear Ordering Problem: given a ground set $N$ of cardinality $n$ and a non-negative set function $f \colon 2^N \rightarrow \mathbb{R}_{\geq 0}$, the goal is to find an ordering $\pi$ of $N$ that minimizes the sum of the values of $f$ over all prefixes of $\pi$. This problem has been studied for various classes of set functions, and the case of a submodular $f$ is of special interest, as it captures classic problems including Minimum Linear Arrangement and Minimum Containing Interval Graph.
In this work, we resolve the approximability of the Minimum Linear Ordering Problem for a general submodular $f$ by establishing matching upper and lower bounds and present: $(1)$ a polynomial-time algorithm achieving an $O(\sqrt{n/\ln n})$-approximation; and $(2)$ a matching information-theoretic hardness result, showing that no algorithm evaluating $f$ a polynomial number of times can achieve an $o(\sqrt{n/\ln n})$-approximation. Previously, the best known hardness of approximation was $2$, and an $O(\sqrt{n/\ln n})$-approximation was known only for the special case where $f$ is both submodular and symmetric.
Blogger's Review: This paper makes significant progress in the study of the submodular linear ordering problem, providing effective polynomial-time algorithms and information-theoretic bounds on hardness, opening new avenues for researchers in related fields, and having a profound impact on optimization algorithm design.