Possible Winner问题参数算法研究及核心化

给定候选人集合C,部分投票的集合P=(v1,v2,…,vn)和候选人c∈C,是否存在P的拓展P′=(v′1,v′2,…,v′n),使得c∈r(P′).该问题在不同的得分规则下复杂性是不同的.该文在分析Betzler的文章中(m-k)-approval得分规则的基础上,提出了possible winner问题在k-approval规则下的动态规划算法,并给出了3-approval规则下possiblewinner问题的多项式核.