g*******y
发帖数: 1930 | 1 很简单的问题模型，N个选区，每个选区有m个人，每人投票给政党A或者B，你事先知道
了每个选区的投票结果，你想作弊，把N个选区划分为2个大选区，每个大选区由N/2个
小选区组成。你希望你所支持的政党在两个大选区都获胜(票数和过半)。
用更数学的语言讲，an integer set{m1,...mN}，0<=mi<=m, partition this set
into two subset each with N/2 elements, such that the sum of each subset >=
N*m/4
这个问题是NP的? NPC的？或者有polynomial算法？
谢谢～ | b***e
发帖数: 1419 | 2 Construct a polynomial reduction from the set partition problem.
Set partition: Given a set A of size n, find out a subset B of A such
that sum(B) = sum(A)/2. In such cases, we call B a partition of A.
1. Let A1 = A \union Z_n, where Z_n is the set that contains n 0's.
So the size of A1 is 2*n. There is a partition of A if and only if
there is a partition of A1 whose size is exactly n.
2. Let a_m = max(A1). Let A2 = {a + 1000 * a_m | a <- A1}. This step
is to make sure the elements | g*******y
发帖数: 1930 | 3 Good idea to consider set partition
But I think there's a flaw, in election zone problem, a valid partition will
result in that the sum of subset falls within a certain range.
For example, m1, m2, m3 ... m_n are votes for party A:
M = sum of {m1...m_n}
a subset with n/2 element: {m_i1, m_i2,...m_i(n/2)}
X = sum of {m_i1, m_i2,...m_i(n/2)}
a valid partition requires:
nm/4 < X < M-nm/4
which means the target subset sum is a range, not a single value;
in contrast, in the Subset NPC problem, the tar
【在 b***e 的大作中提到】
: Construct a polynomial reduction from the set partition problem.
: Set partition: Given a set A of size n, find out a subset B of A such
: that sum(B) = sum(A)/2. In such cases, we call B a partition of A.
: 1. Let A1 = A \union Z_n, where Z_n is the set that contains n 0's.
: So the size of A1 is 2*n. There is a partition of A if and only if
: there is a partition of A1 whose size is exactly n.
: 2. Let a_m = max(A1). Let A2 = {a + 1000 * a_m | a <- A1}. This step
: is to make sure the elements
| b***e
发帖数: 1419 | 4 It is mostly the same.
If there are less supporters of party A than that of party B, then
there's no way to cheat. My reduction reduces to the case where A and
B have same number of supporters, where the best you can get is to tie
in both big election zones.
If you insist the algorithm only solves the case where the supporters
of A is at least 2 more than the supporters of B (which is the
necessary condition for A to beat B in both big zones), then simply
add a further reduction step:
* Let A3 |
|
