Questions tagged [subset-sum]
Questions about the NP-complete problem Subset Sum.
85
questions
0
votes
1answer
28 views
Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T
Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for ...
3
votes
2answers
80 views
Subset Sum With Interval Target
Define the subset sum with interval target problem (SSITP) as follows:
SSITP Input:
A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$ such that $\sum_{a_i \in S} a_i = T$.
SSITP Output:
...
1
vote
0answers
40 views
Does an FPTAS exist for the multiple subset sum problem when m is fixed and c is not a variable?
From Wikipedia Multiple subset sum: The multiple subset sum problem (MSSP) is a generalization of the subset sum problem (SSP): given a multiset $S$ of $n$ integers, and an integer $m$, the goal is to ...
1
vote
1answer
49 views
SUBSET SUM reduction to PARTITION
This is the PARTITION problem:
Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets.
This is the SUBSET SUM problem:
Given a multiset S of integers ...
2
votes
1answer
87 views
Is there an FPTAS for 3-way number partitioning?
The maximization problem of the 3-way number partitioning reads as follows:
given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...
0
votes
1answer
23 views
Prove SubsetSum is polyequivalent to SubsetSum with surplus
I'm solving problem 13.17 of What can be computed?, which is asking to prove $\text{SubsetSum} \equiv_{P} \text{SubsetSumWithFives}$.
Here is the definition of SubsetSumWithFives.
SUBSETSUMWITHFIVES: ...
1
vote
1answer
34 views
Algorithm for computing the sum of symmetric sums (better than $\mathcal{O}(2^N)$ )
Let denote $\mathbf{x} = \{x_1,x_2,...,x_N \}$ with $x_i \in \Bbb R$ for $i=1,...,N$ and $f(\mathbf{x},n)$ be the $n$-th symmetric sum of the set $\mathbf{x}$
$$
f(\mathbf{x},n) = \sum_{\sigma_1,...,\...
0
votes
1answer
50 views
The subset sum problem is not in P because the question is about lossy compressed data? Why not?
Where is there a gap or error in my reasoning?
The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1).
The compression ...
1
vote
1answer
29 views
Reduction from SUBSET-SUM to 0-1-INT-PROG
The 0-1-INT-PROG problem is given an integer $m \times n$ matrix $A$ and an integer $m$-vector $b$, is there an integer $n$-vector $x$ with $A \cdot x \leq b$.
I am trying to prove that 0-1-INT-PROG ...
0
votes
1answer
63 views
Minimum absolute value of subset sums of integer values
$f(x_1,...,x_m)=\min_{\emptyset\subset I\subseteq[m] }\left|\sum_{i\in I}x_i\right|, x_i\in \mathbb{Z}\setminus\{0\}$
How to prove $f\in \mathbf{POLY} \Leftrightarrow \mathbf{P}=\mathbf{NP}$?
When $\...
0
votes
2answers
79 views
Have I proven P equals NP if I find an amortized O(n) algorithm for Subset Sum
I have found an algorithm that runs quite fast on Subset Sum problem few years ago (sometime around 2016). It basically sorts the input set in descending order (instead of the regular ascending) and ...
0
votes
0answers
17 views
Given an abstract argumentation framework, is there a tool that can compute: conflict free, admissible and all extensions?
I am trying to find an online/offline tool that can compute the following:
Given an abstract argumentation framework <S, R>, where S = {a1, a2, a3, a4, a5} and the attack relation
R = {(a1, a2),(...
0
votes
1answer
562 views
How to prove that the subset sum problem is polynomially reducible to the knapsack problem
I want to prove that the subset sum problem is polynomially reducible to the Knapsack problem. Overall I want to show that Knapsack is NP-complete.
There are two parts to showing knapsack is NP-...
1
vote
0answers
51 views
Get $n^{\mathrm{th}}$ element of sorted subset sums
I have a sorted multiset (size < 100, real valued) and want to determine the $n^{\mathrm{th}}$ largest of all possible subset sums (including multiplicity in the sums).
Attempt at solving :
I have ...
0
votes
0answers
56 views
Subset selection with maximum sum and minimum variance?
So I am trying to tackle a combinatorial optimization problem and would like some insights on how to approach it. The problem statement is as follows: Consider a set of elements of size N, how do I ...
0
votes
0answers
16 views
Showing that Subset Sum Reduces to 3-Partition [duplicate]
Given a set of integers S (positive and negative, may contain duplicates) can S be divided into three disjoint subsets that all sum to the same value? Prove this problem is NP-complete.
This is a ...
0
votes
1answer
75 views
Reduce Subset-Sum to Sat
Is there a reduction from SUBSET-SUM to SAT?
Just general SAT, not 3-SAT.
Also the given multiset S only has positive integers.
SUBSET-SUM is defined as follows:
Input: a multiset S = { x1 , ... , xn }...
1
vote
1answer
57 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
32 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
57 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
1answer
42 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
99 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
50 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
57 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
81 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
410 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
126 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
76 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) \...
4
votes
1answer
92 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
333 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
470 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 + ...
3
votes
1answer
27 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
189 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
64 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
93 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
144 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
71 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
136 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
117 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
669 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
64 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
38 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
81 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
351 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
675 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
107 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
117 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
128 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 ...