### 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 |