A note on maximizing the minimum voter satisfaction on spanning trees
A fair spanning tree of a graph maximizes the minimum satisfaction among individuals given their preferences over the edges of the graph. In this note we answer an open question about the computational complexity of determining fair spanning trees raised in Darmann et al. (2009). It is shown that the maximin voter satisfaction problem under choose-t elections is -complete for each fixed t>=2.
Year of publication: |
2010
|
---|---|
Authors: | Darmann, Andreas ; Klamler, Christian ; Pferschy, Ulrich |
Published in: |
Mathematical Social Sciences. - Elsevier, ISSN 0165-4896. - Vol. 60.2010, 1, p. 82-85
|
Publisher: |
Elsevier |
Keywords: | Minimal spanning tree Social choice Fairness |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
Finding socially best spanning trees
Darmann, Andreas, (2011)
-
Maximizing the minimum voter satisfaction on spanning trees
Darmann, Andreas, (2009)
-
Darmann, Andreas, (2015)
- More ...