TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 31.01.2013

isti-logo

Page Content

to Navigation

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.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe