Arrow Research search

Author name cluster

Boting Yang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

22 papers
1 author row

Possible papers

22

AAMAS Conference 2025 Conference Paper

Approximation Ratio for Preference Aggregation Using Tree CP-Nets

  • Abu Mohammad Hammad Ali
  • Daniel Ogundare
  • Boting Yang
  • Sandra Zilles

Aggregating preferences of multiple entities is a problem that has been studied in various models of preference representation, including Conditional Preference Networks (CP-nets). Since optimal aggregation of CP-nets (for a specific natural choice of objective function) is known to require exponential time, efficient approximation algorithms have been proposed in the literature, yet with very limited results on the corresponding approximation ratio. In this paper, we show that a very simple and efficient method yields a 4 3 -approximation for aggregating CP-nets from a proper superset of the set of all tree CP-nets—a well-studied class of CP-nets of relevance to many applications.

PDF

AAAI Conference 2024 Conference Paper

Approximation Algorithms for Preference Aggregation Using CP-Nets

  • Abu Mohammad Hammad Ali
  • Boting Yang
  • Sandra Zilles

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.

PDF Details DOI