TU Berlin

Research Group Algorithmics and Computational ComplexityTalk 19.04.2012

isti-logo

Page Content

to Navigation

On Measuring Nearly Single-Peakedness

Robert Bredereck (Ph.D. Student TU Berlin)

Many problems in context of voting are NP-hard in general. However, when the elections are single-peaked some voting problems become polynomial-time solvable. Often, real-world elections are not perfectly single-peaked, because some voters behave unexpectedly or few candidates do not fit into the model. In our work in progress, we investigate two distances measuring almost single-peakedness. The first distance is "the number of voters to remove to make the election single-peaked", which is also known as number of mavericks in the literature. The second distance is "the number of candidates to remove to make the election single-peaked". We show NP-hardness for the first distance as well as fixed-parameter algorithms computing both distances. Furthermore, we show that there exist effective data reduction procedures (leading to so-called polynomial-size problem kernels) useful for computing these distances (and the corresponding solution sets).

Date
Speaker
Location
Language
19.04.2012 16:15
Robert Bredereck
FR 6510
german/english

Back to the research colloquium site.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe