In the OrderedPartition
problem, the input is two sequences of $n$ positive integers, $(a_i)_{i\in [n]}$ and $(b_i)_{i\in [n]}$.
The output is a partition of the indices $[n]$ into two disjoint subsets, $I$ and $J$, such that:
- $\sum_{i\in I} a_i = \sum_{j\in J} a_i$
- For all $i\in I$ and for all $j\in J$: $b_i\leq b_j$.
In other words, we have to first order the indices on a line such that the $b_i$ are weakly increasing, and then cut the line such that the sum of the $a_i$ in both sides is the same.
If all $b_i$ are the same, then condition 2 is irrelevant and we have an instance of the NP-hard Partition
problem.
On the other hand, if all $b_i$ are different, then condition 2 imposes a single ordering on the indices, so there are only $n-1$ options to check, and the problem becomes polynomial. What happens in between these cases?
To formalize the question, define by OrderedPartition[n,d]
, for $1\leq d\leq n$,
the problem restricted to instances of size $n$, in which the largest subset of identical $b_i$-s is of size $d$. So the easy case, when all $b_i$-s are different, is OrderedPartition[n,1]
, and the hard case, when all $b_i$-s are identical, is OrderedPartition[n,n]
.
More generally, For any $n$ and $d$, in any OrderedPartition[n,d]
instance, the number of possible partitions respecting condition 2 is $O(n 2^d)$. Hence, if $d\in O(\log{n})$, then OrderedPartition[n,d]
is still polynomial in $n$.
On the other hand, for any $n$ and $d$, we can reduce from a Partition
problem with $d$ integers to OrderedPartition[n,d]
. Let $p_1,\ldots,p_d$ be an instance of Partition
. Define an instance of OrderedPartition[n,d]
by:
- For each $i\in \{1,\ldots,d\}$, let $a_i := 2n\cdot p_i$ and $b_i := 1$.
- For each $i\in \{d+1,\ldots,n\}$, let $a_i := 1$ and $b_i := i$
[if $n-d$ is odd, make $a_n:=2$ such that the sum will be even].
Hence, if $d\in\Omega(n^{1/k})$, for any integer $k\geq 1$, then OrderedPartition[n,d]
is NP-hard.
QUESTION: What happens in the intermediate cases, in which $d$ is super-logarithmic but sub-polynomial in $n$?