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。

使用 CP-Nets 进行偏好聚合的近似算法

Approximation Algorithms for Preference Aggregation Using CP-Nets

If a question cannot be answered with the available information, robust
systems for question answering (QA) should know _not_ to answer. One way to
build QA models that do this is with additional training data comprised of
unanswerable questions, created either by employing annotators or through
automated methods for unanswerable question generation. To show that the model
complexity of existing automated approaches is not justified, we examine a
simpler data augmentation method for unanswerable question generation in
English: performing antonym and entity swaps on answerable questions. Compared
to the prior state-of-the-art, data generated with our training-free and
lightweight strategy results in better models (+1.6 F1 points on SQuAD 2.0 data
with BERT-large), and has higher human-judged relatedness and readability. We
quantify the raw benefits of our approach compared to no augmentation across
multiple encoder models, using different amounts of generated data, and also on
TydiQA-MinSpan data (+9.3 F1 points with BERT-large). Our results establish
swaps as a simple but strong baseline for future work.

一种用于问题回答的数据增强方法，通过对可回答问题进行反义词和实体交换生成不可回答的问题，相比于现有的自动化方法，该方法具有更好的模型性能和更高的人类判断相关性和可读性，并被验证为未来工作的简单但强大的基准。