标题： $\{s,t\}$-子模函数的分离主划分序列 显示英文标题

标题： $\{s,t\}$-Separating Principal Partition Sequence of Submodular Functions

摘要： Narayanan 和 Fujishige 展示了次模函数的主划分序列的存在性，这是一种在聚类、快速算法和近似算法等领域有广泛应用的结构。 在这项工作中，受两个应用的启发，我们发展了次模函数的$\{s,t\}$-分离主划分序列理论。 我们定义了这个序列，证明了它的存在性，并设计了一个多项式时间算法来构造它。 我们展示了两个应用：(1) 对单调和正模函数的$\{s,t\}$-分离次模$k$-划分问题的近似算法，以及 (2) 一个多项式时间算法，用于解决超图定向问题，以找到一个同时具有至少$k$的强连通性和至少$\ell$的$(s,t)$-连通性的定向。 显示英文摘要

摘要： Narayanan and Fujishige showed the existence of the principal partition sequence of a submodular function, a structure with numerous applications in areas such as clustering, fast algorithms, and approximation algorithms. In this work, motivated by two applications, we develop a theory of $\{s,t\}$-separating principal partition sequence of a submodular function. We define this sequence, show its existence, and design a polynomial-time algorithm to construct it. We show two applications: (1) approximation algorithm for the $\{s,t\}$-separating submodular $k$-partitioning problem for monotone and posimodular functions and (2) polynomial-time algorithm for the hypergraph orientation problem of finding an orientation that simultaneously has strong connectivity at least $k$ and $(s,t)$-connectivity at least $\ell$.