Computing the minimal covering set

被引:20
作者
Brandt, Felix [1 ]
Fischer, Felix [1 ]
机构
[1] Univ Munich, Inst Informat, D-80538 Munich, Germany
关键词
social choice theory; minimal covering set; essential set; uncovered set; computational complexity;
D O I
10.1016/j.mathsocsci.2008.04.001
中图分类号
F [经济];
学科分类号
02 ;
摘要
We present the first polynomial-time algorithm for Computing the minimal covering set of a (weak) tournament. The algorithm draws upon a linear programming formulation of a subset of the minimal covering set known as the essential set. On the other hand, we show that no efficient algorithm exists for two variants of the minimal covering set - the minimal upward covering set and the minimal downward covering set - unless P equals NP. Finally, we observe a strong relationship between von Neumann-Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other. (C) 2008 Elsevier B.V. All rights reserved.
引用
收藏
页码:254 / 268
页数:15
相关论文
共 38 条