Questions tagged [subset-sum]

Questions about the NP-complete problem Subset Sum.

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

Find the smallest subarray with sum larger than a threshold

Given a set of $n$ positive numbers $\{a_1,\ldots,a_n\}$ and a positive target $T$, find a subset $S$ from $\{a_1,\ldots,a_n\}$ of contiguous elements, that is $S=\{a_i,a_{i+1},a_{i+2},\ldots\}$ for ...
zebda's user avatar
  • 109
0 votes
0 answers
42 views

HAMILTONIAN PATH AND SUBSETSUM

If we were to discover a deterministic algorithm capable of deciding, in polynomial time, whether a given graph contains a Hamiltonian path, would that imply that the problem SUBSETSUM belongs to P? ...
Drat's user avatar
  • 1
3 votes
0 answers
74 views

Subset sum problem with big items

Consider the variant of the Subset Sum problem, where the input is a list of $2 m + 1$ positive integers of sum $2 S$, and the goal is to find a subset with the largest sum that is at most $S$. The ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
51 views

Is this variant of multiset covering problem NP-hard?

Consider this variant of multiset covering problem. Input: a collection of sets $S = \{s_1, s_2, \ldots, s_n\}$ and a universal set $U$, in which $s_k \subseteq U$ and $s_k \neq \emptyset$ for all $k$...
Josh's user avatar
  • 11
0 votes
0 answers
43 views

Understanding David Pisinger's balanced algorithm for the subset-sum problem with bounded weights

I'm trying to understand David Pisinger's balanced algorithm for the subset-sum problem with bounded weights, which can be found on page 5 of his paper Linear Time Algorithms for Knapsack Problems ...
Pablo Messina's user avatar
0 votes
1 answer
50 views

Efficient algorithm for finding the target sum

Task. Find such natural numbers a1,. . . , am , that none of them would be included in the list of excluded numbers, a1 + · · · + am = N and max{a1 , . . . , am} would be as small as possible. Numbers ...
jamesw1's user avatar
0 votes
0 answers
32 views

List of weakly NP-HARD problems

I need a list of at least 10 weakly NP-HARD problems. I already know the Knapsack problem, partition problem and subset sum problem. Please introduce other weakly NP-hard problems to me.
Soroush Vahidi's user avatar
0 votes
0 answers
22 views

Maximum Subset Sum with Pairwise Constraints

(Note: I am posting after reading some possibly related posts because I could not find a fitting solution.) Given some finite set of nodes $S$, where each node $s_i \in S$ has a value $val(s_i) \in [0,...
JustBlaze's user avatar
0 votes
0 answers
20 views

reduction from partition to N3DM or balanced 3 partition problem

I want to know how can I reduce Subset Sum or Partition problem to N3DM problem in which each set has exactly 3 elements and same sum. N3DM Problem: https://en.wikipedia.org/wiki/Numerical_3-...
user's user avatar
  • 1
3 votes
1 answer
148 views

Linear-time constant-space 1/2-approximation algorithm for the maximum subset sum problem

The following problem statement is given: Let $S = \{s_1, s_2, \cdots, s_n\}$ be a sequence of unique positive integers and $K$ a positive integer, where $K \ge s_i$ for every $i$ between $1$ and $n$. ...
asparagus's user avatar
2 votes
1 answer
55 views

Disjoint Subset Sum Reduction (NP-Complete)

I am using past materials to review for an upcoming assignment and came across this question: Disjoint Subset Sum: Input: A set of integers S and a goal g(in the set of natural numbers) Output: YES if ...
abby richardson's user avatar
0 votes
0 answers
57 views

Polynomial Time Special Case of Subset Sum Problem

From Chapter 35 of Introduction to Algorithms by Cormen et al. EXACT-SUBSET-SUM is an exponential-time algorithm in general, although it is a polynomial-time algorithm in the special cases in which $...
ihsingh2's user avatar
1 vote
1 answer
379 views

Finding equal-sum subsets from two arrays

Consider the following problem: You are given two integer arrays $A$ and $B$ of size $N$ and $M$, respectively. You are guaranteed that $1 <= A[i] <= M$ and $1 <= B[i] <= N$ for all $i$ (...
Christopher Miller's user avatar
0 votes
1 answer
84 views

Possible reduction from SUBSET-SUM

Given is a multiset $S$, a finite set $T = \{t_1, t_2, t_3\}$, and an integer $k \in \mathbb{N}$. Let $v(t_j)$ be a set of values $\in \mathbb{R^+}$ of length $|T|$ that can be assigned to $s_i$, and $...
joachimkristensen's user avatar
1 vote
1 answer
181 views

3-Dimensional Matching $\leq$ $_{p}$ subset sum Explanation

excuse me, could someone explain to me the reduction of the problem 3-dimensional matching to subset sum? I was reading Jon Kleinberg's design algorithms book and when I came across this reduction I ...
Emma3201's user avatar
0 votes
2 answers
65 views

Unlimited use subset sum

Given a finite set of integers $Z$ and a number $z$, I would like to check if there exists a subset $A=\left\{ a_1,...,a_{\left| A\right|}\right\}\subseteq{Z}$ and a set of $\left| A\right|$ numbers $...
Benicio Agüero's user avatar
0 votes
1 answer
45 views

I'm looking for an algorithm to find all subsets of a set S with subset sums between a given min and max

Given a set S of numbers, min and max. Find all sebsets of numbers from S with a subset sum larger or equal to min and smaller or equal to max. The following article says that there's an algorithm ...
איתן ליכטמן's user avatar
1 vote
1 answer
35 views

Finding all zero sums of length m and checking for zero subsums on an abelian group (generalization of the sub sum problem?)

Let $G$ be an abelian group. We say that $G$ has property $V_n$ if for every $m > n$ and a list $L\subset G$ of $m$ elements s.t. $\sum_{g\in L}g=0$ there is a proper subset $\emptyset\neq L'\...
levav ferber tas's user avatar
0 votes
1 answer
133 views

Finding number of combinations of numbers from multiple arrays that add up to a given value

Let $ A $ be an array of $ n $ integer arrays with unknown lengths and $ s \in \mathbb{Z} $ a given number. I want to find the number of combinations of numbers from each array, such that their sum ...
talopl's user avatar
  • 101
0 votes
0 answers
125 views

Is there linear solution for the hotel problem

You are going on a trip from point $s$ to point $f$, in the way there are $n$ hotels, $p_1, p_2,..., p_n$ each denotes the number of $km$ from $s$. You must complete the trip by at most $t$ days ($t&...
CforLinux 's user avatar
1 vote
0 answers
82 views

Is there a pseudopolynomial time algorithm for this subset sum variant?

The subset sum problem is: given a list of $n$ positive integers, and a positive number $T$, find a sub-list with largest sum that is at most $T$. The problem can be found in time polynomial in $n$ ...
Erel Segal-Halevi's user avatar
1 vote
0 answers
73 views

Given a set, generate all permutations whose sums are less or equal to a given number

I am looking for a way to generate every permutation (so order does matter) of a set of positive numbers whose sum is less than (or equal to) a given limit. I need to find the permutations themselves, ...
charon25's user avatar
  • 121
0 votes
0 answers
361 views

Proving the load balancing problem is NP-Complete

The load balancing problem: Given we have $m\ge3$ machines (servers) $M_{1}, M_{2},\dots,M_{m}$. As input we are given $n$ jobs defined by their processing times: $t_{1},t_{2},\dots,t_{n}\in\mathbb{Q}...
Guts's user avatar
  • 49
0 votes
1 answer
177 views

Is SUBSET SUM only for positive integers in P or NP?

Since UNARY SUBSET SUM is in P, and a positive-only SUBSET SUM problem could be represented in unary, I struggle to see why it wouldn't be the case that it is in P, when restricted to positive numbers?...
Dragoș Constantin's user avatar
1 vote
1 answer
36 views

Similar problem to Subset Sum?

I've been trying to search for a problem which I think could be similar to Subset Sum. The definition of the problem would be as follows: Given k $\in$ $\mathbb{Z}$ and S = {$s_1$,...,$s_n$} s.t. $s_i ...
Maitgon's user avatar
  • 23
0 votes
0 answers
315 views

Python closest subset sum function

I'm writing a closestSubset(s,A) function that takes an integer s and an array of positive integers A and returns an array consisting of elements of A which add up to s. If there is no subset that ...
LLMM's user avatar
  • 1
2 votes
1 answer
95 views

Is this set covering problem NP-Hard?

Consider this variant of set covering problem. Input: a collection of sets $S = \{s_1, s_2, \ldots, s_n\}$ and a universal set $U$, in which $s_k \subseteq U$ for all $k$. The problem is, divide $S$ ...
zqq's user avatar
  • 69
4 votes
1 answer
124 views

Is there a name for this modification to the subset sum problem?

Let $S = \{\{x_{1},y_{1},z_{1}\},\{x_{2},y_{2},z_{2}\}, \ldots, \{x_{n},y_{n},z_{n}\}\}$ and a target $t$. Let $S_i$ be the subset list $\{x_{i},y_{i},z_{i}\}$. Find a subset sum that sums to $t$ such ...
Joshua's user avatar
  • 49
3 votes
1 answer
102 views

Subset sum with only two item types

Suppose we have $r$ copies of the integer $a$ and $t$ copies of the integer $b$, and a capacity $C$. We would like to find the maximum sum of the given integers, that is at most $C$. This is a special ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
97 views

Subset Sum With Interval Integer Target

Define the subset sum with interval integer target problem (SSIITP) as follows: SSIITP Input: A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$. An integer $T$. SSIITP Output: True, if ...
Samuel Bismuth's user avatar
1 vote
3 answers
128 views

Convert float array to lower or higher integer, find sum(integers) == round(sum(floats)), reducible to subset sum?

You have an array of floats, for example: ...
Pradip Malina Biondi's user avatar
1 vote
1 answer
47 views

In terms of P=?NP, would a P time solution to Subset-Sum have to work in P time when there is no subset that sums to T in the input?

This question is asking for clarification on what P=?NP is asking specifically. I've read the official problem description: here and it seems like P=?NP is primarily concerned with inputs that result ...
Garrick White's user avatar
2 votes
2 answers
325 views

Complexity of a variant of Subset Sum problem

This is the variant of SSP: Given $n$ positive integer points $a_1, \ldots, a_n$ which are all at most $n$, does there exist a subset $\{a_i\}_{i \in P}$, such that its summation is exactly $n+1$? My ...
Haoran Zhu's user avatar
1 vote
1 answer
645 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 ...
joelsh's user avatar
  • 11
3 votes
2 answers
417 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: ...
Samuel Bismuth's user avatar
1 vote
0 answers
148 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 ...
Samuel Bismuth's user avatar
1 vote
1 answer
683 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 ...
Legend123's user avatar
  • 113
2 votes
1 answer
177 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 ...
Samuel Bismuth's user avatar
0 votes
1 answer
44 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: ...
user138389's user avatar
1 vote
1 answer
60 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,...,\...
NN2's user avatar
  • 113
0 votes
1 answer
208 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 ...
Pajzano's user avatar
  • 33
1 vote
1 answer
415 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 ...
Tom Finet's user avatar
  • 258
0 votes
1 answer
90 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 $\...
ChaosPredictor's user avatar
0 votes
2 answers
105 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 ...
vinaych's user avatar
  • 17
1 vote
1 answer
6k 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-...
Ronit sharma's user avatar
1 vote
0 answers
53 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 ...
dripset_pushbert's user avatar
0 votes
0 answers
118 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 ...
sumanyu muku's user avatar
0 votes
2 answers
502 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 }...
Amy's user avatar
  • 1
1 vote
1 answer
194 views

Confusion about dynamic programming on unconstrained subset sum vs constrained subset sum

In class, we discussed two problems: 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: Given an ...
user123215321631443's user avatar
0 votes
0 answers
42 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 ...
DUO Labs's user avatar
  • 289