This paper studies the design and analysis of approximation algorithms for
aggregating preferences over combinatorial domains, represented using
Conditional Preference Networks (CP-nets). Its focus is on aggregating
preferences over so-called \emph{swaps}, for which optimal solutions in general
are already known to be of exponential size. We first analyze a trivial
2-approximation algorithm that simply outputs the best of the given input
preferences, and establish a structural condition under which the approximation
ratio of this algorithm is improved to $4/3$. We then propose a polynomial-time
approximation algorithm whose outputs are provably no worse than those of the
trivial algorithm, but often substantially better. A family of problem
instances is presented for which our improved algorithm produces optimal
solutions, while, for any $\varepsilon$, the trivial algorithm can\emph{not}\/
attain a $(2-\varepsilon)$-approximation. These results may lead to the first
polynomial-time approximation algorithm that solves the CP-net aggregation
problem for swaps with an approximation ratio substantially better than $2$.

该论文研究了设计和分析适用于将组合领域中使用条件偏好网络（CP-nets）表示的偏好进行聚合的近似算法。它侧重于对所谓的 “交换” 进行偏好聚合，其中已知的最优解通常具有指数规模。我们分析了一个简单的 2 近似算法，该算法仅输出给定输入偏好中的最佳解，并确定了一种结构条件，在此条件下改进了该算法的近似比率为 4/3。然后，我们提出了一种多项式时间逼近算法，其输出的解证明不会比简单算法差，但通常更好。我们提出了一族问题实例，对于这些问题实例，我们改进的算法产生最优解，而对于任何 ε 值，简单算法都不能获得（2-ε）近似解。这些结果可能导致首个在多项式时间内解决 CP-net 聚合问题的近似算法，其近似比率明显优于 2。