贪心即排序：新颖性指标的精确且可认证理想排序
原标题：When Greedy Is Sorting: Exact and Certified Ideal Rankings for Novelty Metrics
AI 摘要
该论文研究新颖性排序指标（α-nDCG、ERR-IA）中理想排序的计算问题。作者发现，当每个文档最多只对一个意图有正增益（行支持为一）时，理想排序可精确且高效地计算：通过指标特定的虚拟分数变换与多路归并（ChainMerge），在 O(n+K log G) 时间内得到全局最优 top-K 排序，替代 NIST ndeval 等实现中 Θ(nK) 的贪心近似。当意图判断重叠时，精确优化在标准设置下为 NP-hard，作者给出一个多项式规模 LP 上界，可为贪心分母提供全局最优性证书；在 TREC Web 2009–2012 数据上，该 LP 证明 198 个查询中 189 个贪心分母全局最优，并在 MIND-small 上 ChainMerge 比贪心快 17–1011 倍。
正文节选
When Greedy Is Sorting: Exact and Certified Ideal Rankings for Novelty Metrics Abstract. The ideal ranking that normalizes novelty metrics is NP-hard to compute in general, so widely used \(\alpha\)-nDCG evaluators approximate its denominator with a greedy rule that rescans every remaining document at each rank. We identify a regime in which this ideal ranking is exact and cheap for both \(\alpha\)-DCG and intent-aware expected reciprocal rank (ERR-IA). When each document is positively judged fo