16 maja 2017 10:15
[Seminarium ZOK] Krzysztof Sornat: "Proportional Approval Voting, Harmonic k-median, and Negative Association"
Wtorek, 10:15-12:00, sala 310.
Streszczenie. We study Proportional Approval Voting (PAV)---an election system used for choosing representatives bodies, such as parliaments, based on preferences of a population of voters over individual candidates. We observe that the problem of computing the outcome of PAV can be cast as a variant of the standard k-median problem. Our main result is that, due to the specific (harmonic) cost structure, the problem allows constant factor approximation that does not require the underlying connection costs to be metric. To the best of our knowledge this is the first constant factor approximation algorithm for a facility location type problem not assuming triangle inequalities for connection costs.
The algorithm we propose is a standard dependent rounding routine (DR) [Srinivasan FOCS'01] applied to the solution of a natural LP-relaxation of the problem. The rounding process is well known to produce distributions over integral solutions satisfying Negative Correlation (NC). For fixed tournament trees DR has even much stronger property called Conditional Negative Association (CNA). To the best of our knowledge stronger property than NA was never used---NC was enough. However, NC is not sufficient for our analysis. We show a simple proof that, if the rounding process follows a predefined tournament tree, dependent rounding has a stronger property that we call Binary Negative Association (BNA). We also show that if the pairs of elements to be correlated are being selected by an adaptive adversary, then the BNA may not hold, while the proof of NC does not depend on the order of selection of elements.
Joint work with Jarosław Byrka and Piotr Skowron. Electronic version of the paper at https://arxiv.org/abs/1704.021