使用 CP-Nets 进行偏好聚合的近似算法
原文中文，约400字，阅读约需1分钟。发表于：。该论文研究了设计和分析适用于将组合领域中使用条件偏好网络（CP-nets）表示的偏好进行聚合的近似算法。它侧重于对所谓的 “交换” 进行偏好聚合，其中已知的最优解通常具有指数规模。我们分析了一个简单的 2 近似算法，该算法仅输出给定输入偏好中的最佳解，并确定了一种结构条件，在此条件下改进了该算法的近似比率为...
该论文研究了使用CP-nets表示偏好的聚合近似算法，通过改进算法结构条件，提高了近似比率。同时，提出了一种多项式时间逼近算法，其解证明通常比简单算法更好。这些结果可能导致首个在多项式时间内解决CP-net聚合问题的近似算法，其近似比率明显优于2。
