Questions tagged [subset-sum]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
-3
votes
1answer
170 views

Can we map this problem to subset-sum?

Let there be $n$ set of ordered pairs $s_1=\{(c_1,f_1),(c_1,f_2) ...(c_1,f_m)\}$, $s_2=\{(c_2,f_1),(c_2,f_2) ...(c_2,f_m)\}$, $s_3=\{(c_3,f_1),(c_3,f_2) ...(c_3,f_m)\}$, .... $s_n=\{(c_n,f_1)(c_n,f_2) ...
10
votes
1answer
362 views

An obstruction like ETH

We know under $ETH$ we cannot solve $K$-SUM in $f(K)poly(nK)$ time under any function $f(K)$ (usually $2^{O(K)}$). Is there any conjecture that prevents a $(\log n)^{O(K)}$ complexity (this is ...
4
votes
0answers
223 views

Difficulty of graph coloring and independent set?

Given a graph on $n$ vertices it is strongly $NP$-complete to decide it is $3$-colorable while it is easy to decide it is $n$-colorable. Is there a parsimonious reduction from SUBSET-SUM to GRAPH-3-...
3
votes
0answers
238 views

new subset sum approach results

I have been working on a new approach for a subset sum exact solver, and the current state provides an algorithm operating on $O{n/2 \choose n/4}$, demonstrating as well the hardest target value is ...
0
votes
1answer
143 views

Subset Sum Problem and hard looking instances that are not really hard

I have been working in a subset sum solver (some new approach) and while working on the time complexity analysis I found what I describe below. Maybe this could explain why some "hard looking" ...
1
vote
1answer
102 views

A dominate vector subset sum problem

Let $k$ be some constants (e.g. one can take $k=2$ for simplexity), for any $u,v\in \mathbb{R}$, we say $u$ dominate $v$ if $\forall 1\le i\le k,~ u[i]\ge v[i]$, write it as $u\succ v$. Consider the ...
2
votes
1answer
129 views

Is partitioning a multiset into two multisets with equal averages NP-complete?

The subset sum problem of partitioning a multiset of integers into two multisets with equal sums is NP-complete. Is the seemingly related problem of partitioning a multiset of integers into two ...
0
votes
0answers
109 views

What definition for $FPT$ algorithm for $KSUM$ gives $W[P]=FPT\implies KSUM$ is $FPT$?

In the definition on $KSUM$ problem we are given $n$ input integers and we have to decide if $K$ of them sum to $0$. $KSUM$ is $FPT$ if there is a $O(f(K)poly(n))$ algorithm for it. However Downey ...
12
votes
0answers
433 views

Is satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ NP Complete?

Question I would like to show that satisfying $\sum_{i=1}^{n}{x_i^{y_i}}=r$ is NP-Complete. Consider $L= \{(\bar{y},r):\exists \bar{x} \text{ such that } \sum_{i=1}^{n}{x_i^{y_i}}=r\}$. Where $\...
2
votes
2answers
525 views

Strongly NP-complete variants of subset sum or partition problem

Some problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's GI result). However, the fixed-point free GA ...
4
votes
1answer
204 views

Interesting real life problem similar to subsetsum /bin packing problem

I have a real life scenario, where I need to solve a construction related problem somewhat similar to bin packing problem.The situation is as follows : I have large number of cable reels/drums (let's ...
1
vote
0answers
182 views

At what parameters is following $NP$-hard?

Problem Instances at given $\alpha>0$. $(1)$ Given $a_1,\dots,a_{n^\alpha}\in\Bbb Z$ with $|a_i|\in(2^{n-1},2^n-1)$ is there a subset of that sums to $0$? $(2)$ Given $a_1,\dots,a_{n}\in\Bbb Z$ ...
2
votes
2answers
526 views

Subset product problem

We have $m$ list of integers $L_1,\dots,L_m$ and each list $L_i$ contains $n$ distinct integers $L_i(1),\dots,L_i(n)$. You are given two integers $a$ and $b$ with $b<a$ and we know $n=O(2^{(\log b)...
0
votes
1answer
186 views

Complexity of $r$-sum as a function of integer sizes

Given $n$ distinct integers whose absolute value is of size $c_{n,k}=\lceil n^{1/k}\rceil$ bits ($c_{n,k}$th bit position is always $1$ for absolute value) we know that using dynamic programming we ...
3
votes
1answer
258 views

Variant of Subset Sum Problem with Changing Bound

Given a sequence of decreasing integers, i.e., $a_1 \geq a_2 \geq \cdots \geq a_T $ and a positive real $k\geq 1$, find a subset $S$ such that $$\max_{S\subseteq \{1,\ldots,T\}} \sum_{i\in S} a_i$$ $$...
5
votes
1answer
344 views

On Zero sum perfect matching

Fix $c\geq1$. Input is a $m$ vertex complete graph with edges assigned $a_1,\dots,a_{\frac{m(m-1)}2}\in\Bbb Z$ in some order. Is it $\mathsf{NP}$-complete to decide if there is a perfect matching of ...
-4
votes
1answer
206 views

NP-completeness of one generalized subset sum problem (target sum belongs to interval) [closed]

I need to prove that decision problem: for a given set of positive integers $a_1, ..., a_n$, does it exist a subset that sums up to a value within interval $[\frac{1}{2}\sum a_i; \frac{1}{2}\sum a_i+...
0
votes
2answers
407 views

NP completeness of linear $0-1$ assignment problem

Supposing we have a linear equation in $n^2$ variables with integer (negatives allowed) coefficients of at most $m$ bits each. Partition $\Pi_1$ the variables into $n$ disjoint sets of $n$ variables ...
7
votes
2answers
805 views

“Any” Subset Sum. Is it hard?

Here is a variant of the classic partition problem: Given a list of integers can it be partitioned into $S_1$, $S_2$, and $S_3$, with $S_1$ and $S_2$ nonempty, so the sum of elements in $S_1$ equals ...
7
votes
1answer
245 views

Does this problem related to subset sum have a name?

I'm looking for research into this problem -- computational complexity, solution algorithms, approximation algorithms, etc. If it has a canonical name, that would help me look into prior research. ...
1
vote
1answer
456 views

Subset sum with many targets

Take a set $S = \{a_1, a_2, ..., a_n\}$ of integers $a_i$ and a set $G = \{b_1, b_2, ..., b_m\}$ of integers $b_j$. If we ask the question, is there a subset $C \subseteq S$ such that the sum $(\sum_{...
4
votes
1answer
230 views

Is the problem NP-C or polynomially solvable?

I am considering a problem of the following: Given a set $X$ of integers and another integer B, are there two subsets of $X$, say $X_1$ and $X_2$, such that $X_1-X_2=B$ ? (Here, $X_i$ also denotes the ...
1
vote
1answer
321 views

NP-hardness of minimizing sum of weighted product

Consider a total of $d$ items, $\{I_1,I_2,\cdots,I_d\}$, each having a weight $w_i$ (a positive integer), and a total of $m$ bins, $\{B_1,B_2,\cdots,B_m\}$. We would like to distribute the items into ...
2
votes
1answer
330 views

Complexity class of a subset problem similar to subset sum

What could be the complexity class of the following problem: Given a positive integer $K$, a positive integer $d$ (say $2$) and a set $S$ of all non-negative integers less than $K$ find a $S' \...
13
votes
1answer
335 views

Another variant of PARTITION

I've got a reduction of the following partition problem to a certain scheduling problem: Input: A list $a_1\leqslant\cdots\leqslant a_n$ of positive integers in non-decreasing order. Question: Does ...
9
votes
0answers
795 views

Faster pseudo-polynomial time algorithm for subset-sum?

Let $S(X) = \{\sum_{i\in Y} i | Y\subset X \}$, the set of subset sums of $X$. $S_n(X) = S(X)\cap \{1,\ldots,n\}$. Consider the following variant of subset sum. ALL-SUBSET-SUMS INPUT: positive ...
13
votes
1answer
463 views

Is DAG subset sum approximable?

We are given a directed acyclic graph $G=(V,E)$ with a number associated with each vertex ($g:V\to \mathbb{N}$), and a target number $T\in \mathbb{N}$. The DAG subset sum problem (might exist under a ...
2
votes
1answer
551 views

Subset Sum bounds

Are there any bounds for the subset problem with respect to the number of the terms involved in the sum and the range of the possible values?For example looking for some 2 terms whose sum equals 3 you ...
5
votes
1answer
530 views

Combining subset sum and subset product problems

The subset sum problem and subset product problem are NP-complete. Is the following problem polynomial-time solvable: given a set of positive integers, find a subset whose sum is $S$ and whose product ...
2
votes
1answer
781 views

Multiple subset sum where subsets have complementary cardinality

$\underline{\mathsf{EQUAL\mbox{ }k-COMPLEMENTARY\mbox{ }SUBSET\mbox{ }SUM(EkCSS)} }$Problem: Input: $a_1,\dots,a_n,b\in \mathbb Z$, with distinct $a_i$ and $k\in\Bbb Z^+$. Output: $k$ $\mbox{ }\...
15
votes
3answers
3k views

Subset sum vs. Subset product (strong vs. weak NP hardness)

I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard. Subset Sum: Given $X = \{x_1,...,...
8
votes
1answer
793 views

Interesting SUBSET-SUM problems

I know the following variants of SUBSETSUM problems: $ \mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L} $ (Elberfeld at. al., 2010), NP-complete $ \mathtt{SUBSETSUM} $, and NEXP-complete $ \mathtt{...
8
votes
1answer
2k views

What are good approximation algorithms for the subset sum problem so far?

By "good", I mean either the algorithm provides a relatively tight bound or it has a relatively fast running time. Any reference is welcome.
6
votes
3answers
1k views

Complexity of a subset sum variant

Given integers $a_1, \ldots, a_n, b \in \mathbb{N}$. What is the complexity of the following problem $$ \exists x_1, \ldots, x_n \in \mathbb{N} \text{ such that } a_1x_1 + \ldots a_nx_n = b? $$ I ...
6
votes
1answer
2k views

SUBSET-SUM with binary - unary - “positional” encoding

I don't know if my question is too simple (I'm not an expert, so feel free to delete it) SUBSET-SUM (given a set of integers $<x_{1},...,x_n>$, find if the sum of one or more non-empty subset ...
14
votes
1answer
882 views

Integer relation detection for Subset Sum or NPP?

Is there a way to encode an instance of Subset Sum or the Number Partition Problem so that a (small) solution to an integer relation yields an answer? If not definitely, then in some probabilistic ...