The Next Best Solution

Ronen I. Brafman, Enrico Pilotto, Francesca Rossi, Domenico Salvagnin, Kristen Brent Venable, Toby Walsh

AAAI 2011 pp. 1537-1540

doi:10.1609/AAAI.V25I1.7958 /aaai/2011/brafman2011aaai-next/

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.

PDF AAAI Semantic Scholar

Cite

Text

Brafman et al. "The Next Best Solution." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.7958

Markdown

[Brafman et al. "The Next Best Solution." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/brafman2011aaai-next/) doi:10.1609/AAAI.V25I1.7958

BibTeX

@inproceedings{brafman2011aaai-next,
  title     = {{The Next Best Solution}},
  author    = {Brafman, Ronen I. and Pilotto, Enrico and Rossi, Francesca and Salvagnin, Domenico and Venable, Kristen Brent and Walsh, Toby},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {1537-1540},
  doi       = {10.1609/AAAI.V25I1.7958},
  url       = {https://mlanthology.org/aaai/2011/brafman2011aaai-next/}
}