Tight Algorithm and Hardness for Submodular Linear Ordering (opens in new tab)

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 includ...