Max Planck Institute for Informatics

Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number

Abstract We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that comput...

Distortion of Multi-Winner Elections on the Line Metric: The Polar Comparison Rule

We study the problem of minimizing metric distortion in multi-winner elections, where a committee of size k is selected from a set of candidates based on voters’ ordinal preferences. We assume that voters and candidates are embedded on a line metric, and social cost is determined...