我们考虑最小线性排序问题：给定一个基集 $N$，其基数为 $n$，以及一个非负集合函数 $f \colon 2^N \rightarrow \mathbb{R}_{\geq 0}$，目标是找到一个 $N$ 的排序 $\pi$，以最小化 $\pi$ 的所有前缀值的总和。这个问题在各种集合函数类别中都有研究，尤其是子模函数 $f$ 的情况，因为它涉及经典问题，如最小线性排列和最小包含区间图。
本文解决了子模函数 $f$ 一般情况下的最小线性排序问题的可近似性，通过建立匹配的上下界，我们提出：$(1)$ 一个在多项式时间内实现 $O(\sqrt{n/\ln n})$ 近似的算法；$(2)$ 一个匹配的信息论难度结果，表明任何多项式次数评估 $f$ 的算法都无法实现 $o(\sqrt{n/\ln n})$ 的近似。之前已知的最佳近似难度为 $2$，而 $O(\sqrt{n/\ln n})$ 的近似仅在 $f$ 同时为子模和对称的特殊情况下已知。
博主点评： 本文在子模线性排序问题的研究上取得了重要进展，提供了有效的多项式时间算法和信息论的难度界限，为相关领域的研究者开辟了新的思路，尤其对优化算法设计具有深远影响。