Questions tagged [subset-sum]

Questions about the NP-complete problem Subset Sum.

Filter by
Sorted by
Tagged with
1
vote
1answer
17 views

Unconstrained subset sum vs constrained subset sum?

In class, we discussed two question types: constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by. Question 1: ...
0
votes
0answers
31 views

Is is possible to create a SUBSET-SUM instance that each subset is “unique”?

Given a SUBSET-SUM instance $S$ with a weight $W$, is it possible to create, in polynomial time, a new non-empty instance $T$ (at most the same length as $S$) with weight $M$, that for each non-empty ...
0
votes
1answer
45 views

How can you modify a SUBSET-SUM instance so evaluating a set outputs either 0 or 1?

An SUBSET-SUM instance is a list of $n$ integers $\{ a_1, a_2,... a_n\}$. To evaluate a subset is to output the sum of a subset. However, I want to know, is it possible to create a new instance $T$, ...
0
votes
0answers
26 views

Are inputs of NP problems too implicit?

I'm reading on wikipedia about P vs NP and I have a question. Consider the zero sum problem: given a set of integer A, determine if there is a non empty subset such that the sum of all its elements is ...
0
votes
1answer
16 views

Multi-dimensional Knapsack with Minimum Value constraints for Dimensions

In MDK, we have a vector $W = \{W_1, W_2, ..., W_d\}$ where each element corresponds to the maximum weight for the respective dimension in the knapsack. I want to add a conditional constraint: $V = {...
1
vote
1answer
70 views

Dataset of Hard Instances of SUBSET-SUM

I know for factoring we have the RSA Numbers, in which factoring one of them quickly (usually) indicates a breakthrough in the field. However, I want to know if there's something similar for SUBSET-...
1
vote
1answer
39 views

Converting a Mixed SUBSET-SUM Problem To All-Positive Case

Let's say we have a SUBSET-SUM problem with list {$x_1,x_2,x_3,...x_N$} and weight $W$, with some of $x_i<0$. Is there a known way, in polynomial time, to convert this problem into an equivalent ...
0
votes
2answers
47 views

Complexity of Subset Sum where the size of the subset is specified

I know it should be easy but I'm trying to determine the complexity of the following variant of Subset Sum. Given a subset $S$ of positive integers and integers $k>0$ and $N>0$, is there a ...
0
votes
3answers
75 views

Find the smallest group of numbers with sum bigger then $X$

Given a list of numbers $S$ where $0 < s_i < 100$, find the minimum sum group of numbers with a sum bigger than $X$. Each number can be used multiple times. Ex: for $S = [3,4.1], X = 10$ the ...
0
votes
1answer
160 views

How to realize applicable meet-in-the-middle algorithm for 0-1 Knapsack?

I am now studying Knapsack Problem (KP), and find the Meet-in-the-middle algorithm described in Wikipedia a little unclear that, how to realize it in the theoretical time complexity of $O^*(2^{n/2})$? ...
0
votes
0answers
44 views

How to trace Subset from Boolean DP table in the Subset Sum Problem

I have seen that the Subset Sum Problem can be solved using Dynamic programming and we should look up the Last row's last column to return the result. My questions are. How did someone conclude that ...
2
votes
1answer
58 views

How to prove the NP-completeness of MOD-PARTITION

MOD-PARTITION: Given a set of integers $A={a_1,...,a_n}$, their weights $w = \{w_1, w_2, \dots, w_n\}$ and the number $k$, does there exist a subset $X$ of $A$ such that: $(\sum_{x \in X} w(x) * x) \...
2
votes
1answer
71 views

Enumerate all valid orders of subset sums

Given an positive integer $n$, we define an order of subset sums (or simply, an order, when there is no ambiguity) to be a sequence of all subsets of $\{1,\ldots,n\}$. For example, when $n=2$, the ...
4
votes
1answer
126 views

Two versions of Subset Sum Problem

I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is: Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, ...
9
votes
2answers
338 views

Subset sum problem for permutations

Given permutations $g_1,\,\ldots, g_m \in S_n$ of size $n$ and target permutation $g \in S_n$, decide if there exists a subset of $\{g_1,\, \ldots, g_m\}$, which composition in some order (or, ...
2
votes
0answers
37 views

Finding a non negative combination of integers that adds up to a certain number [duplicate]

I have a set of positive numbers: ${n_1,n_2,...n_k}$ s.t. $n_1>n_2>\dots >n_k$. I want to find an array of non-negative integers $c_1,c_2,\dots,c_k$ such that $$n_1c_1 + n_2c_2 + \dots + ...
0
votes
0answers
26 views

Subset sum reduction to 3SAT [duplicate]

I have gone over numerous proofs that reduce 3SAT to Subset sum reduction and then claim equivalence, however the other direction is never coherently explained in these proofs. In particular the proof ...
3
votes
1answer
24 views

Solve SUBSET SUM for Reciprocals of Primes

Let $p_1, ..., p_n$ distinct prime numbers with $P = \prod_{i=1}^{n}{p_i}$ and $A=(a_1, ..., a_n)$ with $a_i = P/p_i$. Problem Show the SUBSET SUM problem $(A, \alpha)$ can be solved in polynomial (...
1
vote
1answer
119 views

Return the subset with smallest cardinality of an array whose elements sum to at least a given value

Suppose we are given an array $A[1\ldots n]$ and a value $C$. Is there an algorithm with linear expected runtime that can produce an array that is the subset with smallest cardinality of $A[1\ldots ...
2
votes
1answer
43 views

complexity of a variant of the subset sum problem

We have a set of positive integers $N=\{a_1,...,a_n\}$, we want to select a subset $N'$ of $N$ with maximum total sum of integers such that this sum should not exceed a given integer $B$. What is the ...
2
votes
1answer
73 views

find maximum sum of xors

we are given an Array Array size <= 10^4 . 0 <= A[i] <= 15 We need to partition the array into 4 subsets (each subset can have zero or more elements ). Take xor of each subset and sum ...
2
votes
2answers
121 views

Minimizing the iterative sum of pairs of numbers in a list

Given the tuple (list, value): $$\left(\left[x_1, x_2, \cdots x_n\right], y\right)$$ You may choose two adjacent values in the list to modify the tuple as: $$\left(\left[x_1, x_2, \cdots x_{i-1}, (...
1
vote
1answer
70 views

Divide a number in k powers of 2

Example N = 9 and K=3 4 + 4 + 1 = 9 . What I have tried. We can not go on dividing with 2. We can use unbounded knapsack with array elements from 2^0 to 2^32.
1
vote
0answers
108 views

multiset variant of subset sum problem known algorithms

I have been working in the time analysis for an exact solver I designed for the subset sum problem accepting multisets as input instances, and determined its time complexity to be dependent on the ...
2
votes
1answer
116 views

Find N best subset of quotations

I am faced with the following problem; We are provided cost quotations for shipping cost per packet by various shipping companies, let's call these quotations $Q_1 ... Q_k$. Each Quotation is a $M \...
1
vote
1answer
455 views

Generate all combinations of values that are less than array's elements and have a sum = target

I want to find a way to generate sets that contain elements that sum to a certain target. Initially, I have an array that contains elements representing the maximum value that can be stored in that ...
1
vote
1answer
46 views

Recover boolean vector from dot products

Question: I want to determine a boolean vector $b \in \{0,1\}^n$ consisting of zeros and ones, but cannot access it directly. I can only call a black-box computer code which will take the dot product ...
0
votes
0answers
35 views

Finding fixed size submatrix with highest sum

I have a matrix, which has N rows and M columns. I need to find n rows and m columns, which has the highest sum. Matrix consists of positive numbers. Not optimal solutions are ok. For example N=M=4; n=...
0
votes
1answer
65 views

Prove Subset-Sum is NP-complete - Alternative reduction?

It is well known the Subset-Sum problem is NP-complete. This can be shown using a reduction from the 3SAT problem. I am wondering: is there any other NP-Complete problem that could be reduced to the ...
0
votes
1answer
196 views

Time complexity of subset sum problem with reals instead?

It is well known that the conventional subset sum problem with integers is NP-complete. What if the array elements can be any real numbers and also target sum can be any real number? Is it NP-complete ...
0
votes
1answer
168 views

Find all subsets with a given sum

How to choose from a set of positive numbers all the subsets that sum to some number x? For example if the set $S=[1,1,2,3,4,5,6,7]$ and I'm searching for all the subsets that sum to $7$ I would have $...
1
vote
1answer
97 views

Finding the Range of Solutions for KSum Variation

Preface I asked a question before where I was looking to understand the complexity class of the following problem: Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such ...
2
votes
1answer
88 views

Counting the number of subsets with positive sum

I have some constant vector $\mathbf{s}$ on $n$ dimensions, where every element of $\mathbf{s}$ is a real number, and I would like to multiply it by every possible $n$-dimensional binary vector $\...
1
vote
1answer
100 views

Job scheduling approximation

In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf Lemma 5 is given as: The approximation factor of the modified greedy [scheduling] algorithm is 4/3....
0
votes
1answer
1k views

Partition array into k subsets

We are given an array and a number K. Partition array into K subsets such that let MaxSum be the maximum sum of among subsets. We have to minimize summation =$$\sum_{i=1}^{k}MaxSum-sum(i) $$ Is ...
0
votes
1answer
45 views

invariant of bin packing

We are given an array of integers and a number K. We need to pack these integers into bins. The condition is that we have to use exactly K number of bins and each bin should have equal capacity. We ...
1
vote
0answers
24 views

Given a subset of numbers $1, \dots, n$, find the minimal subset of numbers $1, \dots, n$ sums of every subset of which cover all sums of first subset

Given a subset $A = \{a_1, a_2, \dots, a_k\}$ of numbers $\{1, 2, \dots, n\}$, find another subset $B = \{b_1, b_2, \dots, b_t\}$ of numbers $\{1, 2, \dots, n\}$ of minimal size (that is, minimise $t$)...
1
vote
1answer
54 views

Does a polynomial solution to weakly-NP Complete problem mean P = NP?

Suppose someone finds a polynomial solution to weakly-NP Complete problem does that mean P = NP.
4
votes
0answers
202 views

Subset Sum Search Problem for Input with At Most One Solution [closed]

Edit: This question has been reasked on TCS. We first consider the search version of the subset sum problem: Given a set $S$ of $n$ naturals, find a subset of $S$ that sums to exactly $W$. My ...
2
votes
2answers
299 views

Check if K-Sum Variation is NP-Complete

Problem Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$. Question This problem came from evaluating some scheduling algorithms that I am ...
0
votes
0answers
16 views

Intuitively, my problem is a mix of perfect hashing, tree spanning, combinatorial stuff - Ordered Decision Tree?

The problem I'm trying to solve is difficult to to give a single name, but I'll call it the ordered decision tree problem. Imagine a row of commands: ...
2
votes
3answers
497 views

N subsets with a given sum?

How to efficiently ¹⁾ choose from a set of numbers $S$, a given number $n$ of disjoint subsets, each with a given sum $K$ of chosen elements? ¹⁾ Not as in $P$, I just want something smarter than $O(n^...
1
vote
0answers
63 views

Find a partition of multiset of binomial coefficients with constriants

Given the multiset $S$ where the elements are defined by the binomial coefficient ${n \choose k}$ where $n \in \mathbb{N}$ and $ 0\leq k \leq n$ find the partition $P$ of $S$ such that the sum of ...
1
vote
1answer
162 views

Reducing subset sum to even subset sum

I'm trying to learn reduction. I have this problem called "even subset sum" that's very similar to subset sum. It's the same problem as as subset sum except that the only numbers allowed are even ...
2
votes
1answer
1k views

Proof of NP Completeness of set-partition problem

I have reduced subset sum problem to set partition problem but do not know whether it is correct and so I need your help. MY METHOD In subset sum problem we have to find a subset $S_1$ of set $S$ so ...
1
vote
1answer
62 views

Subset sum problem, given that a valid subset exists

I have a problem at work. I need to find a subset of a set of positive integers that sums to a certain value. I know there is a subset but I need to find it. Is this new problem the same as the ...
1
vote
1answer
192 views

Subset sum exponential solution - how does the sorting work?

The wiki for the subset sum problem found here it states that you take the list of N elements and split it into two lists of N/2 elements. You then generate all the subsets for each list (each having ...
1
vote
1answer
47 views

How to find sets of polynomially bounded numbers whose subset sums are different?

Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
1
vote
1answer
159 views

Is this an $NP$-complete problem: Product-2-Partition

I want to prove the NP-hardness of some problem P in scheduling theory. I was trying with Partition, 3-Partition and Subset product, But neither was successful. Now, I can reduce a problem, say ...
2
votes
1answer
520 views

Maximum Equal Sum K Subsequences

Given an array we need to find maximum equal sum $K$ subsequences, i.e. we want the sum to be maximized such that there are exactly $K$ non-overlapping subsequences each having the same sum. Example: ...