direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Es gibt keine deutsche Übersetzung dieser Webseite.

Are there any nicely structured preference profiles nearby?

Dipl.-Inform. Jiehua Chen (TU Berlin)

We investigate the problem of deciding whether a given preference profile is close to a nicely structured preference profile of a certain type, as for instance single-peaked, single-caved, single-crossing, value-restricted, best-restricted, worst-restricted, medium-restricted, or group-separable profiles. We measure this distance by the number of voters or alternatives that have to be deleted so as to reach a nicely structured profile. Our results classify all considered problem variants with respect to their computational complexity, and draw a clear line between computationally easy (polynomial time solvable) and computationally intractable (NP-hard) questions.

Date
Speaker
Location
Language
31.01.2013 16:15
Jiehua Chen
TEL 512
english

Back to the research colloquium site.

Zusatzinformationen / Extras