8 citations · 13 across the 5 of their papers we have counts for
5 papers · 1 filter
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…
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…