科研之友
微信
新浪微博
Facebook
分享链接
摘要
Assume that each of n voters may or may not approve each of m issues. If an agent (the lobby) may influence up to k voters, then the central question of the NP-hard LOBBYING problem is whether the lobby can choose the voters to be influenced so that as a result each issue gets a majority of approvals. This problem can be modeled as a simple matrix modification problem: Can one replace k rows of a binary n x m-matrix by k all-1 rows such that each column in the resulting matrix has a majority of 1s? Significantly extending on previous work that showed parameterized intractability (W[2]-completeness) with respect to the number k of modified rows, we study how natural parameters such as n, m, k, or the %26quot;maximum number of 1s missing for any column to have a majority of 1s%26quot; (referred to as %26quot;gap value g%26quot;) govern the computational complexity of LOBBYING. Among other results, we prove that LOBBYING is fixed-parameter tractable for parameter m and provide a greedy logarithmic-factor approximation algorithm which solves LOBBYING even optimally if m %26lt;= 4. We also show empirically that this greedy algorithm performs well on general instances. As a further key result, we prove that LOBBYING is LOGSNP-complete for constant values g %26gt;= 1, thus providing a first natural complete problem from voting for this complexity class of limited nondeterminism.
- 出版日期2014
