# Tag Info

11

Here is an outline of a reduction from PARTITION to UNIQUE PARTITION. Suppose the original numbers are $x_1,\ldots,x_n$ and the target is $T$. I assume that all $x_i$ are positive integers. The new numbers are going to be $2^n x_i + i$, as well as $1,2,4,\ldots,2^{n/2}$, and the new target is $2^n T + 2^{n/2}$. (The numbers $2^n,2^{n/2}$ are quite arbitrary ...

8

I'm going to make a few guesses as to what you precisely mean, and if they're correct, we can edit the question so everything is clearer. First I'll define what I think you mean with your problem: Input: A set of positive integers $A=\{a_{1}, \ldots, a_{n}\}$. Question: Is there a set of integers $P = \{p_{1}, \ldots, p_{n}\}$ such that for each $i$ ...

7

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-... 7 The current expectation is that most likely there is no efficient (polynomial-size, polynomially-verifiable) way to do that. The partition problem is NP-complete. For a NP-complete problem, we have an efficient way to certify that the answer to the question is YES, but not necessarily any efficient way to certify that the answer is NO. If you find an ... 6 Karmarkar and Karp do not claim that the second problem is NP-complete. It can't be, because it is not in NP. Remember that NP is a class of decision problems, i.e., problems where the answer is either "yes" or "no". Because the problem is not in NP, it's not required that the answer be efficiently checkable. The same thing happens with TSP: sure, if I ... 6 I'm not familiar with the topic, so all I can do is give a few pointers. Manipulating partitions of finite sets is known by several names: union-find when you start with singletons and progressively merge sets; partition refinement when you start with a single set and progressively split it; union-split-find when sets can be both merged and split as in your ... 6 You can use the way that the recurrence formula below is derived to find your encoding: $$B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k.$$ This is proved by consider how many other elements are in the part containing the element$n+1$. If there are$n-k$of these, then we have$\binom{n}{n-k} = \binom{n}{k}$choices for them, and$B_k$choices for partitioning ... 4 You're absolutely right that this partition always occurs. If you consider what this means in terms of the corresponding subset, you'll find that this indicates that the empty set (which is always a subset) has sum 0. In fact, this indicates the there is always a solution to subset sum when the target is 0, which is exactly as expected. It turns out fixing ... 4 Even in an unweighted graph, your suggested algorithm doesn't work: take a graph of 6 vertices with triangle a, b, c, and triangle d, e, f, with an edge between c and d. Vertices a, b, e, and f each have minimal degrees of 2, but cutting the graph between the two triangles gives a cut of 1. 4 I think this could work. We multyply all the numbers by fifteen and we also multiply$B$, the quantity that each "bucket" should add to, by fifteen and we add twelve to it. Then we add twelve numbers of size one for each bucket to the input. As twelve is less than fifteen, we have to use exactly twelve of them to fill each bucket, then we have to use other ... 4 Hint: find a recurrence$f(n, k)$that tells you in how many different ways you can sum to$k$using the first$n$integers (ignoring order and using numbers at most once). Then the answer to your problem is$\frac 1 2 f(n, n(n+1)/4)$. The trick is to realize that the sum of$P$, is$S= \displaystyle \sum_{k=1}^n = \frac{1}{2}n(n+1)$, and that if you ... 4 The following is directly taken from pages 358-360 of The Nature of Computation by Moore and Mertens and I think addresses your problem directly. Imagine that you run a computer center with$p$identical machines, or a parallel computer with$p$processors, for some constant$p$. You are given$n$jobs with running times$t_1,t_2,...,t_n$. Your task is to ... 3 You are looking for an optimal 1-dimensional k-means algorithm. The k-means objective function for partitioning the data$x_1, \ldots, x_n$into$k$sets$S = \{S_1, \ldots, S_k\}$. $$\sum\limits_{i=1}^k \sum\limits_{x \in S_i}\lVert x - \mu_i \rVert^2$$ where$\mu_i$is the mean of$S_i$[1]. You can apply a dynamic programming algorithm to the ... 3 Is it in NP? Yes - any restricted version of an NP problem is also in NP. Is it still NP-hard? Yes. 2-partition (without the constraint that both subsets should be equal cardinality) is NP-hard. Let's call your form of the problem "equal cardinalty 2-partition". To reduce from regular 2-partition to equal cardinalty 2-partition, we can pad the 2-partition ... 3 When$k,s$are upper-bounded by a constant, the problem can be solved in polynomial time. Call a multiset$T$good if its sum is at least$s$, and if removing any one element causes the sum to fall strictly below$s$, and if all elements are in the set$\{1,2,\dots,k-1\}$. How many good multisets are there? Well, since$k$and$s$are constants, the ... 3 An offset is a difference between two indices, usually memory locations or array indices. For example, suppose that you have an array$A$in which each element occupies$x$bytes. Suppose also that the address of$A$is$M$. Then the address of the$i$th element (counting from zero) is$M + i \cdot x$. Here$i \cdot x$is the offset. It's the difference ... 3 Suppose first that we fix the sizes of the sets$|A_i| = n_i$in non-decreasing order$n_1 \leq \cdots \leq n_k$. In that case, if we arrange the numbers$a_i$in non-decreasing order, then an optimal choice is $$A_1 = \{a_n,\ldots,a_{n-n_1+1}\}, A_2 = \{a_{n-n_1},\ldots,a_{n-n_1-n_2+1}\}, \ldots, A_k = \{a_{n_k},\ldots,a_1\}.$$ The reason is that given ... 3 Use dynamic programming. This is a straightforward application of dynamic programming. This is a very nice exercise, so I'll let you do the exercise yourself and won't spoil it for you -- but since you only wanted a hint, my hint is "use dynamic programming" (that's a huge, enormous hint that should be enough for you to work out the rest of the details). ... 3 Section 5.10 of Ruskey's book Combinatorial Generation gives a combinatorial Grey code for linear extensions of posets and describes a bijection between set partitions of a chosen shape and linear extensions of a corresponding poset. Partitions of Given Type Let$P(n_0, n_1, \ldots, n_t)$be the set of partitions of the set$\{1, 2, \ldots, n\}$into ... 3 Your problem is NP-complete, as proved by Adi Shamir in his paper On the cryptocomplexity of knapsack systems. 3 Yes, your approach is correct. "The interval partitioning problem" is more commonly known as "the interval-graph coloring problem". It is problem 16.1-4 in the book Introduction to Algorithm by CLRS, third edition. The idea behind the common solution described in the question and your approach is essentially the same. Arguably, your algorithm is simpler ... 3 All directed graphs can be edge-partitioned into two subgraphs that are acyclic and therefore triangle free. Let$\prec$be any total ordering of the vertices. For each edge$(u, v) \in A$, put it in$A_1$if$u \prec v$, and in$A_2$otherwise. Both$(V, A_1)$and$(V, A_2)$must be acyclic. 3 I'm assuming by$sum(i)$you mean that given an ordering of the$k$partitioned subsets, sum over all elements of the$i$th subset. The$k=2$case is the optimization variant of the set partitioning problem (https://en.wikipedia.org/wiki/Partition_problem) which is known to be as hard as subset sum. EDIT: The general case is as difficult by reduction from$...

3

The problem is polynomial (even linear time) for any fixed $c < 1/2$. Assume no there is no item of size $> (1-c)S$, otherwise it is a trivial no-instance. If there is any item $w_i$ with size $\geq cS$ we are immediately done because we can take one half of the partition to be that item. Otherwise, all items are $< cS$. Greedily taking items ...

2

Some linear time modular decomposition algorithms use (some type of) partition refinement, see e.g. these algorithms for directed and undirected graphs.

2

Here's an approach that I suspect will work very quickly. I suggest you start by enumerating all possible values for an $S_i$, i.e., all possible 6-element subsets of $S$ that contain exactly one element of $N$ as a subset. How many such sets do you expect to find? By a crude back-of-the-envelope estimate, I estimate there will be only a handful, maybe 10 ...

2

This is a pretty common version of partition and in this case you need N+1 comparisons. For example consider an array containing ${1,2,\ldots,N}$. Now, 1 is your pivot (partitioning item). pivot 1 is compared with first element 1 and it is greater than or equal it, so you got the left item. Here you need 1 comparison. Then, pivot 1 is compared with $N,N-... 2 You can use integer linear programming (ILP) to solve this. In particular, here is how to use an ILP solver to test whether there exists a way to permute the second partition so that you find$k+1\$ alignment points (including the two endpoints). Given an algorithm for this decision procedure, you can use binary search to find the optimal alignment. Call a ...

2

What you are doing here is adding a new element to your original set 'X'. The value for this new element is (s - 2t). Hence, X' now contains one extra element as compared to X. The SET-PARTITION would "accept" if the provided set can be partitioned into two subsets with equal sum. We were already able to pick out a subset 'Y', from the set X, the sum of ...

2

The details depend on the partitioning method used, but usually the pivot ends up in its final position. That follows from the second and third statement, by the way: all elements smaller than the pivot are to the left of it, and the larger to the right. The pivot is in between, and that is clearly its final position in the sorted array. That the second ...

Only top voted, non community-wiki answers of a minimum length are eligible