We consider the Minimum Linear Ordering Problem: given a ground set N of cardinality n and a non-negative set function f: 2^N→ℝ≥0, the goal is to find an ordering π of N that minimizes the sum of the values of f over all prefixes of π. 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(√(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(√(n/ln n))-approximation. Previously, the best known hardness of approximation was 2, and an O(√(n/ln n))-approximation was known only for the special case where f is both submodular and symmetric.
