4
$\begingroup$

The PARTITION problem is NP-complete:

INSTANCE: finite set $A$ and a size $s(a) \in \mathbb{Z}^+$ for each $a \in A$
QUESTION: Is there a subset $A' \subseteq A$ such that $\sum_{a \in A'} s(a) = \sum_{a \in A \setminus A'} s(a)$

The problem remains NP-complete even if the elements are ordered as $a_1,a_2,...,a_{2n}$ and we require that $A'$ contains exactly one of $a_{2i-1},a_{2i}$ for $1 \leq i \leq n$ (Garey and Johnson, Computers and Intractability).

This variant should be known as EVEN-ODD PARTITION.

Do you see a quick reduction to prove its hardness? (or do you know the paper where it was first defined and proved)

$\endgroup$
  • 2
    $\begingroup$ A problem with that name was proven NP-complete in Garey, Michael R., Robert E. Tarjan, and Gordon T. Wilfong. "One-processor scheduling with symmetric earliness and tardiness penalties." Mathematics of Operations Research 13.2 (1988): 330-348. Sorry I can't access the paper right now, but I wonder if this is what you are looking for. $\endgroup$ – Juho Dec 25 '13 at 10:55
  • $\begingroup$ @Juho: to be honest I didn't checked it because it was published in 1988 and the G&J Computers and Intractability (in which the problem is said to be NP complete) was published in 1979 and I was more interested in the reduction (and I found two papers in which they call it EVEN-ODD PARTITION with a reference to G&J for its NP-completeness). However the reduction is very simple (I found it by myself). $\endgroup$ – Vor Dec 25 '13 at 22:29
7
$\begingroup$

Let $b_i = a_{2i} - a_{2i-1}$. The problem is then finding $\sum \varepsilon_i b_i = 0$. Here $\varepsilon_i = 1$ if $a_{2i} \in A'$ and $-1$ otherwise. Let $B' = \{b_i \mid \varepsilon_i = 1\}$. Note that $\sum_{b \in B'} b = \sum _{b \in B \setminus B'} b$. Thus solving PARTITION of $B$ would solve EVEN-ODD PARTITION of $A$.

Let $b_{2i} = a_i$ and $b_{2i-1} = 0$. Note that if $b_{2i} \in B' \leftrightarrow a_i \in A'$ and $\sum_{B'} = \sum_{B \setminus B'}$ then $\sum_{A'} = \sum_{A \setminus A'}$. Thus solving EVEN-ODD PARTITION on $B$ would solve PARTITION on $A$.

$\endgroup$
2
$\begingroup$

Another quick reduction is the following:

Let $2^k > \sum_{a \in A} s(a)$. Then for each element $a_i \in A$ add to $B$ two elements:

$b_{2i-1} = 2^{2k+2i} + a_i$and
$b_{2i} = 2^{2k+2i} + a_i 2^k$.

The two consecutive elements cannot be contained in the same subset (due to the $2^{2k+2i}$ common "bit"), and $B$ can be even-odd partitioned into two equal sum subsets that have the same cardinality if and only if $A$ can be partitioned into two equal sum subsets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.