保序回归学习笔记

和拟阵一样，做一道联合省选题的时候遇到了这个，之前高爸也屡次♂邀请♂我学它，于是就有了本文。

保序回归问题

对于有向无环图$G = (V,E)$，定义代价函数$w$和初态函数$y$，求一个终态函数$f$使得

• 若$(u,v) \in E$，则$f_u \le f_v$。

求$\min \sum_{u\in V} w_u|f_u - y_u|^p$（$1\le p<\infty$）。

另一种形式的保序回归问题，以后再讨论。

特殊情形

当$p=1$，一定存在一个最优解使得$\{f_i\}\subseteq\{y_i\}$。

我们可以对$V$做整体二分，对于区间$[L,R]$假设其中点为$M$，那么我们强制$y_M\le f_i \le y_{M+1}$，也就是说$f_i$的取值只有$\{y_M,y_{M+1}\}$，求最小回归代价。

这是一个 01 决策问题，可以转化为最小权闭合子图问题。

在得到每个点的决策后，对于两边再分别整体二分即可。

最大权闭合子图问题

最大权闭合子图问题为：给出一个带点权的有向图$G=(V,E)$，要求选择$V$的一个子集使得点权和最大，同时满足：若$u$被选那么$u$的后继也要被选。

这个问题可以利用最小割解决。直接把这个有向图当作网络图，$E$中的边容量都为无限大。加入一些新的边：

• 若$u$的点权为正，则加一条$s$到$u$的容量为点权的边；
• 若$u$的点权为负，则加一条$u$到$t$的容量为点权绝对值的边。

对这个图跑最小割，答案即为正权点的和减去最小割的容量。

可以理解为：割一条$(s,u)$的边代表不选这个点，割一条$(u,t)$的边代表选这个点。

一般情形

只要$p<\infty$，那么我们将在$V$上二分更改为在实数集上整体二分即可求出关于某个精度的近似解。

在信息学竞赛中，一般求的是整数解，因此在整数集上二分也可。

参考文献

高睿泉，《浅谈保序回归问题》，IOI2018 中国国家集训队论文。