Skip to main content

Questions tagged [subset-sum]

Questions about the NP-complete problem Subset Sum.

Filter by
Sorted by
Tagged with
3 votes
1 answer
41 views

Harder version of the k-partition problem

Given a sequence $q_1, \ldots, q_n$ of numbers, decide if the set $I=\{1,\ldots,n\}$ can be partitioned into $k$ sets $I_1, \ldots, I_k$ such that $\sum_{i\in I_1} q_i=\sum_{i\in I_2} q_i = \dots = \...
Lisa E.'s user avatar
  • 378
1 vote
0 answers
30 views

NP-hardness of subset sum of multiple supersets

Given the following problem: Input: A set of disjoint sets $s_1, s_2, \dots s_n$, and an integer $K$ Question: Is there a set A with $|A|= n$ and $|s_i \cap A| = 1$ for all i from 1 to n, s.t. $\sum_{...
SimonNW's user avatar
  • 161
0 votes
0 answers
54 views

Why does this approach not work on the SubSet Sum Problem?

I was reading this post, and in it I learned how to make difficult instances of the SubSet Sum Problem. There the guy who responded to the post says that it is necessary to have density 1.0 and all ...
Edu's user avatar
  • 1
1 vote
1 answer
69 views

Subset ${\tt XOR}$ problem

Motivation. This is a variant of the subset sum problem involving the bitwise ${\tt XOR}$ operation. Problem. Given a set $X$ of $n$ bit-strings of length $n$, determine if there is a non-empty subset ...
Dominic van der Zypen's user avatar
1 vote
1 answer
464 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
51 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
82 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
61 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
1 vote
0 answers
65 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
75 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
41 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
23 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
3 votes
1 answer
308 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
141 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
67 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
649 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
101 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
444 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
80 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
47 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
40 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
271 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
160 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
92 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
103 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
465 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
232 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
39 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
406 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
106 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
140 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
117 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
103 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
156 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
49 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
342 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
2 votes
1 answer
777 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
  • 21
3 votes
2 answers
497 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
158 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
829 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
3 votes
1 answer
195 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
72 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
246 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
569 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
91 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
114 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
7k 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
136 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