2023/12/14 by Abu Mohammmad Hammad Ali, Ali, Abu Mohammmad Hammad, Boting Yang +3
Computer Science · Decision Sciences · #Advanced Algebra and Logic #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Multi-Criteria Decision Making
paper · pdf · doi:10.48550/arxiv.2312.09162
openalex publication_date 2023/12/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 ε, the trivial algorithm cannot\/ attain a (2-ε)-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.