Tight Algorithm and Hardness for Submodular Linear Ordering

Abstract

We consider the Minimum Linear Ordering Problem: given a ground set $N$ of cardinality $n$ and a non-negative set function $f:2^N\to {\mathbb{R}}_{\ge 0}$, the goal is to find an ordering $\ddot{I}€$ of $N$ that minimizes the sum of the values of $f$ over all prefixes of $\ddot{I}€$. 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.

25 pages. Accepted to the 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)