8 citations · 13 across the 5 of their papers we have counts for
8 papers
Algorithms for Structured Elections under Thiele Voting Rules
Alexandra Lassota, Krzysztof Sornat
We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by…
Robust Committee Voting, or The Other Side of Representation
Gregory Kehne, Ulrike Schmidt-Kraepelin, Krzysztof Sornat
We study approval-based committee voting from a novel perspective. While extant work largely centers around proportional representation of the voters, we shift our focus to the can…
An O(loglog n)-Approximation for Submodular Facility Location
Fateme Abbasi, Marek Adamczyk, Miguel Bosch-Calvo +4
In the Submodular Facility Location problem (SFL) we are given a collection of clients and facilities in a metric space. A feasible solution consists of an assignment of ea…
Constant-Factor Approximation for Ordered k-Median
Jarosław Byrka, Krzysztof Sornat, Joachim Spoerhase
We study the Ordered k-Median problem, in which the solution is evaluated by first sorting the client connection costs and then multiplying them with a predefined non-increasing we…
Proportional Approval Voting, Harmonic k-median, and Negative Association
Jarosław Byrka, Piotr Skowron, Krzysztof Sornat
We study a generic framework that provides a unified view on two important classes of problems: (i) extensions of the k-median problem where clients are interested in having multip…
Approximation and Parameterized Complexity of Minimax Approval Voting
Marek Cygan, Łukasz Kowalik, Arkadiusz Socała +1
We present three results on the complexity of Minimax Approval Voting. First, we study Minimax Approval Voting parameterized by the Hamming distance from the solution to the vo…
Inequity Aversion Pricing over Social Networks: Approximation Algorithms and Hardness Results
Georgios Amanatidis, Peter Fulla, Evangelos Markakis +1
We study a revenue maximization problem in the context of social networks. Namely, we consider a model introduced by Alon, Mansour, and Tennenholtz (EC 2013) that captures inequity…
PTAS for Minimax Approval Voting
Jaroslaw Byrka, Krzysztof Sornat
We consider Approval Voting systems where each voter decides on a subset to candidates he/she approves. We focus on the optimization problem of finding the committee of fixed size…