Are there any nicely structured preference profiles nearby?

R. Bredereck, Jiehua Chen, G.J. Woeginger

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

24 Citaten (Scopus)


We investigate the problem of deciding whether a given preference profile is close to having a certain nice structure, 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 to make the profile a nicely structured one. Our results classify the problem variants with respect to their computational complexity, and draw a clear line between computationally tractable (polynomial-time solvable) and computationally intractable (NP-hard) questions.

Originele taal-2Engels
Pagina's (van-tot)61-73
Aantal pagina's13
TijdschriftMathematical Social Sciences
StatusGepubliceerd - 1 jan 2016

Vingerafdruk Duik in de onderzoeksthema's van 'Are there any nicely structured preference profiles nearby?'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit