研究表明,通过将方案多样性与参数化复杂性理论相结合,可以使用基于算法的框架解决实际相关问题,例如 Kemeny Rank 聚合问题。
May, 2021
本文介绍使用集合竞赛来将一组输入排名汇总成一个输出排名,引入了 Kemeny 规则的一种泛化版本,其中将最小化 k-wise 不一致的数量作为目标,介绍了大多数图的 k-wise 对应物,并提供了 k-wise Kemeny 聚合问题的近似算法。
Nov, 2019
本文通过左式方法给 Kemeny's rule 一定的广义,探讨了 $3$-wise Kemeny voting scheme 的更多应用和优势,证明了这个方法的非常有用,时空复杂度相较于经典的 Kemeny rule 更优,并且可以防止更多的操纵。
Apr, 2023
通过对代理人的偏好进行赋值,我们将找到 Kemeny 排名作为对抗式武装强盗问题。我们考虑了采样和不采样的情况,并提供了概率近似正确(PAC)解决方案的算法,同时详细说明了其采样复杂度。如果所有代理人的偏好都是对备选项的严格排名,我们提供了剪枝置信区间的方法,以便更有效地赋值,并提出了几种自适应采样方法进行比较。
Dec, 2023
该论文研究了基于 Kemeny 规则的选举中位数共识排名问题,并通过详细说明各种相对排序的实际应用,提出了解决 $3$-wise Kemeny 问题的一些技术方法,使得该问题具有了许多重要的性质和应用。
本文描述并实现了如何使用量子退火器解决 Kemeny Rank Aggregation 问题,并使用 2 种数据缩减规则与模拟退火和局部搜索等经典算法进行对比研究量子退火器的运行时间、解决方案的质量和多样性。
Jan, 2023
给定多个项目之间的成对比较,如何对它们进行排名,以使得排名与观察结果相匹配?本研究关注基于 Erdos-Renyi 异常值(ERO)模型的排名问题,在该问题中,每个成对比较都是真实分数差异的损坏副本。通过研究基于非归一化和归一化数据矩阵的谱排名算法,我们提供了每个项目从观察数据中恢复出其潜在分数的性能,并得出了非归一化 / 归一化数据矩阵的最大特征向量与其总体对应物之间的逐项扰动误差界限。通过留一法技术,我们提供了更精确的最大特征向量的 l∞范数扰动界限,并在只有 Ω(nlogn) 个样本的情况下导出了每个项目的最大偏移误差界限。理论分析在样本复杂度方面改进了现有技术的结果,并通过数值实验验证了这些理论发现。
Sep, 2023
我们研究了三个问题的固定参数算法:Kemeny 排名聚合、反馈弧集锦标赛和在两点之间的锦标赛。
Jun, 2010
本研究旨在通过成对比较的数据形式,使用 Copeland 计数算法实现对 n 个项目的排序,使其具有计算效率高,鲁棒性强,接近信息论极限等特点,并将结果扩展到汉明距离度量下的近似恢复问题和任意错误要求条件下的恢复问题。
Dec, 2015
使用图 Helmholtzian 和组合 Hodge 理论,基于边缘流的成对排名可以解析为两个正交成分,其中一个表示 L2 最优全局排名,而另一个表示无旋转流,同时还可以通过线性最小二乘回归计算离散的 Hodge 分解。
Nov, 2008