# Questions tagged [subset-sum]

The tag has no usage guidance.

53 questions
Filter by
Sorted by
Tagged with
5k views

• 229
443 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 ...
• 13k
3k 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.
• 467
884 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 ...
• 4,479
891 views

• 13k
1k views

73 views

### Partition of a set of integers into subsets where the max. of the subset-sums is minimum

Let $S$ be a set of $n$ positive integers, and $p$ be a partition of $S$ into $m$ mutually disjoint subsets, such that no subset contains more than $k$ elements. Let $\mathcal{P}$ denote the set of ...
116 views

### Can this relaxed subset-sum problem be solved with a smaller dynamic program? [closed]

Cross-post from CS.SE In the subset sum problem, the input is a list of positive integers $x_1,\ldots,x_n$ and an integer $T$, and the goal is to decide whether there is a subset of sum exactly $T$. ...
• 2,262
114 views

536 views

• 412
1 vote
57 views

### Is this a variant of the set cover problem?

$\textbf{Decision Problem:}$ Given a finite set of elements $E$ and a collection $C$ of non empty sets, $C=\{E_1,...,E_n\}$, such that each $E_i$ covers at least one element of $E$. The goal is to ...
1 vote
322 views

### Two valued variant of subset sum problem

I'm interested in the complexity of the following problem: Given a multiset $S$ containing only two positive integers $a$ and $b$, find a $k$-partition of $S$ that maximizes the sum of part with ...
1 vote
184 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$ ...
• 13k
1 vote
18 views

### Is this subset sum NP complete?

In $\mathsf{NP}$ complete subset sum problem we ask 'Given $n$ numbers in $\Bbb Z$ is there a subset that sums to $0$?'. Is problem 'Given $n$ of degree at most $d$ polynomials in $\Bbb Z[x]$ with ...
• 13k
679 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 ...
• 13k
186 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" ...
• 131
321 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 ...
• 271
223 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 ...
93 views

### strong NP-completeness of multi-dimensional Equal-Subset-Sum

I want to show that the multi-dimensional Equal-Subset-Sum is NP-complete in the strong sense: Given a set of $d$-dimensional vectors of non-negative integers, does there exist two distinct nonempty ...
• 101
38 views

### Feature selection problem under promise

Are there well used examples of feature selection problem where the problem is defined under certain promise? Let's say the task is to select the minimum number of features such that the mutual ...
• 651