36 citations · 167 across the 66 of their papers we have counts for
11 papers · 1 filter
Proportionally Representative Participatory Budgeting: Axioms and Algorithms
Haris Aziz, Barton Lee, Nimrod Talmon
Participatory budgeting is one of the exciting developments in deliberative grassroots democracy. We concentrate on approval elections and propose proportional representation axiom…
The Complexity of Multiwinner Voting Rules with Variable Number of Winners
Piotr Faliszewski, Arkadii Slinko, Nimrod Talmon
We consider the approval-based model of elections, and undertake a computational study of voting rules which select committees whose size is not predetermined. While voting rules t…
Reality-Aware Social Choice
Ehud Shapiro, Nimrod Talmon
Social Choice theory generalizes voting on one proposal to ranking multiple proposals. Yet, while a vote on a single proposal has the status quo (Reality) as a default, Reality has…
On The Parameterized Tractability of the Just-In-Time Flow-Shop Scheduling Problem
Danny Hermelin, Dvir Shabtay, Nimrod Talmon
Since its development in the early 90's, parameterized complexity has been widely used to analyze the tractability of many NP-hard combinatorial optimization problems with respect…
Scheduling Two Agents on a Single Machine: A Parameterized Analysis of NP-hard Problems
Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay +2
Scheduling theory is an old and well-established area in combinatorial optimization, whereas the much younger area of parameterized complexity has only recently gained the attentio…
A Participatory Democratic Budgeting Algorithm
Ehud Shapiro, Nimrod Talmon
The budget is the key means for effecting policy in democracies, yet its preparation is typically an excluding, opaque, and arcane process. We aim to rectify this by providing for…
Mixed Integer Programming with Convex/Concave Constraints: Fixed-Parameter Tractability and Applications to Multicovering and Voting
Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier +2
A classic result of Lenstra [Math.~Oper.~Res.~1983] says that an integer linear program can be solved in fixed-parameter tractable (FPT) time for the parameter being the number of…
Robustness Among Multiwinner Voting Rules
Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk +3
We investigate how robust the results of committee elections are to small changes in the input preference orders, depending on the voting rules used. We find that for typical rules…
Balanced Facilities on Random Graphs
Roee David, Nimrod Talmon
Given a graph G with n vertices and k players, each of which is placing a facility on one of the vertices of G, we define the score of the i'th player to be the number of vertices…
Proportional Representation in Vote Streams
Palash Dey, Nimrod Talmon, Otniel van Handel
We consider elections where the voters come one at a time, in a streaming fashion, and devise space-efficient algorithms which identify an approximate winning committee with respec…
When can Graph Hyperbolicity be computed in Linear Time?
Till Fluschnik, Christian Komusiewicz, George B. Mertzios +3
Hyperbolicity measures, in terms of (distance) metrics, how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen int…