201 citations · 1.5k across the 125 of their papers we have counts for
16 papers · 2 filters
Parameterized Complexity Results in Symmetry Breaking
Toby Walsh
Symmetry is a common feature of many combinatorial problems. Unfortunately eliminating all symmetry from a problem is often computationally intractable. This paper argues that rece…
Improving the Performance of maxRPC
Thanasis Balafoutis, Anastasia Paparrizou, Kostas Stergiou +1
Max Restricted Path Consistency (maxRPC) is a local consistency for binary constraints that can achieve considerably stronger pruning than arc consistency. However, existing maxRRC…
Stable marriage problems with quantitative preferences
Maria Silvia Pini, Francesca Rossi, Brent Venable +1
The stable marriage problem is a well-known problem of matching men to women so that no man and woman, who are not married to each other, both prefer each other. Such a problem has…
Where are the hard manipulation problems?
Toby Walsh
One possible escape from the Gibbard-Satterthwaite theorem is computational complexity. For example, it is NP-hard to compute if the STV rule can be manipulated. However, there is…
An Empirical Study of Borda Manipulation
Jessica Davies, George Katsirelos, Nina Narodystka +1
We study the problem of coalitional manipulation in elections using the unweighted Borda rule. We provide empirical evidence of the manipulability of Borda elections in the form of…
Local search for stable marriage problems
M. Gelain, M. S. Pini, F. Rossi +2
The stable marriage (SM) problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools, or more general…