License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.04421.4
URN: urn:nbn:de:0030-drops-1038
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2005/103/
Go to the corresponding Portal

Goldsmith, Judy

Preferences and Domination

pdf-format:
04421.GoldsmithJudy.Paper.103.pdf (0.2 MB)

Abstract

CP-nets are a succinct formalism for specifying preferences over a multi-featured domain. A CP-net consists of a directed graph, with nodes representing the features of the domain, and edges indicating conditional preferences.
An instance in the domain is an assignment of values to the features. An instance alpha is preferred to an instance beta if there are a sequence of "improving flips" from alpha to beta, where an improving flip changes the value of one feature to a more-preferred value, based on the values of the parents of that feature. We say alpha dominates beta if such a sequence exists.
We show that recognizing dominance is PSPACE hard for cyclic CP-nets.

BibTeX - Entry

@InProceedings{goldsmith:DagSemProc.04421.4,
  author =	{Goldsmith, Judy},
  title =	{{Preferences and Domination}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--10},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{4421},
  editor =	{Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2005/103},
  URN =		{urn:nbn:de:0030-drops-1038},
  doi =		{10.4230/DagSemProc.04421.4},
  annote =	{Keywords: Preferences , CP-nets , PSPACE-complete , reductions}
}

Keywords: Preferences , CP-nets , PSPACE-complete , reductions
Collection: 04421 - Algebraic Methods in Computational Complexity
Issue Date: 2005
Date of publication: 24.03.2005

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI