Tag Info

0

W.l.o.g. assume the integers are ordered such that $x_1 \geq \cdots \geq x_n$. @Laakeri presented an algorithm for finding a partition $(A,B)$ that satisfies: $\sum_B + x_1 \geq \sum_A \geq \sum_B - x_1$ His algorithm can be used to finding a partition that satisfies the stronger condition: $\sum_B + \max_{A} \geq \sum_A \geq \sum_B - \max_{B}$ The ...

2

No. Intuitively, the problem gets harder if we take out the restrictions on the input values, since the restricted instances are a subset of the instances of the general problem. However, the article says, even if you introduce this restriction the problem does not get easier and it is still strongly NP-complete. On the other hand, exhaustive search is not ...

3

Your problem is the same as interval graph coloring. There is a well-known greedy algorithm solving the problem optimally, running in linear time if the intervals are already sorted.

3

There is an $O(n \log n)$ algorithm for this problem. To formalize, lets say that the task is to partition $n$ given integers into two partitions $A$ and $B$ that have sizes $a$ and $b$, with $a+b = n$ and $a \le b$. Denote the maximum integer with $M$ and the sums of integers in $A$ and $B$ with $\sum_A$ and $\sum_B$. The partitions should satisfy that \$|\...

Top 50 recent answers are included