# Questions tagged [subset-sum]

The tag has no usage guidance.

53 questions
Filter by
Sorted by
Tagged with
120 views

### Solution to Subset Sum Problem (in some sense) using Gaussian elimination modulo 2

Consider a set of natural numbers $S \in \mathbb{N}^n$ for some $n \in \mathbb{N}$. Assume that each number $s_i = S^T\cdot e_i$ meets $s_i \leq 2^m$ i.e. is written on at most $m$ number of digits, ...
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 ...
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 ...
46 views

### Unbounded Knapsack: Does Increasing capacity increase optimal value?

Our decision problem is as follows: given weights $\mathbf{w}$, values $\mathbf{v}$, and capacities $C_1$ and $C_2$, where $C_1 < C_2$, does the optimal value of unbounded knapsack with the above ...
5k views

1 vote
66 views

30 views

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 ...
1k 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 ...
260 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 ...
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" ...
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 ...
257 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 ...
506 views

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 ...
441 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$$ ...
436 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 ...
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 ...
319 views

236 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
474 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 ...
536 views

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 1 answer 387 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 0 answers 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 ... 8 votes 1 answer 891 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{...
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 ...
$\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{ }\...