A note on maximizing the minimum voter satisfaction on spanning trees

详细信息    查看全文

• 作者：Andreas Darmann ; Christian Klamler ; Ulrich Pferschy
• 关键词：Minimal spanning tree ; Social choice ; Fairness
• 刊名：Mathematical Social Sciences
• 出版年：2010
• 出版时间：July 2010
• 年：2010
• 卷：60
• 期：1
• 页码：82-85
• 全文大小：285 K

文摘

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.