The Next Best Solution

Authors

  • Ronen Brafman Ben Gurion University
  • Enrico Pilotto University of Padova
  • Francesca Rossi University of Padova
  • Domenico Salvagnin University of Padova
  • Kristen Venable University of Padova
  • Toby Walsh University of New South Wales and NICTA

DOI:

https://doi.org/10.1609/aaai.v25i1.7958

Abstract

We study the computational complexity of finding the next most preferred solution in some common formalisms for representing constraints and preferences. The problem is computationally intractable for CSPs, but is polynomial for tree-shaped CSPs and tree-shaped fuzzy CSPs. On the other hand, it is intractable for weighted CSPs, even under restrictions on the constraint graph. For CP-nets, the problem is polynomial when the CP-net is acyclic. This remains so if we add (soft) constraints that are tree-shaped and topologically compatible with the CP-net.

Downloads

Published

2011-08-04

How to Cite

Brafman, R., Pilotto, E., Rossi, F., Salvagnin, D., Venable, K., & Walsh, T. (2011). The Next Best Solution. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 1537–1540. https://doi.org/10.1609/aaai.v25i1.7958

Issue

Vol. 25 No. 1 (2011): Twenty-Fifth AAAI Conference on Artificial Intelligence

Section

New Scientific and Technical Advances in Research