Tight Algorithm and Hardness for Submodular Linear Ordering

Evan Abboud, Roy Schwartz

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…