patternMajor
Generalised 3SUM (k-SUM) problem?
Viewed 0 times
problemgeneralised3sumsum
Problem
The 3SUM problem tries to identify 3 integers $a,b,c$ from a set $S$ of size $n$ such that $a + b + c = 0$.
It is conjectured that there is not better solution than quadratic, i.e. $\mathcal{o}(n^2)$. Or to put it differently: $\mathcal{o}(n \log(n) + n^2)$.
So I was wondering if this would apply to the generalised problem: Find integers $a_i$ for $i \in [1..k]$ in a set $S$ of size $n$ such that $\sum_{i \in [1..k]} a_i = 0$.
I think you can do this in $\mathcal{o}(n \log(n) + n^{k-1})$ for $k \geq 2$ (it's trivial to generalise the simple $k=3$ algorithm).
But are there better algorithms for other values of $k$?
It is conjectured that there is not better solution than quadratic, i.e. $\mathcal{o}(n^2)$. Or to put it differently: $\mathcal{o}(n \log(n) + n^2)$.
So I was wondering if this would apply to the generalised problem: Find integers $a_i$ for $i \in [1..k]$ in a set $S$ of size $n$ such that $\sum_{i \in [1..k]} a_i = 0$.
I think you can do this in $\mathcal{o}(n \log(n) + n^{k-1})$ for $k \geq 2$ (it's trivial to generalise the simple $k=3$ algorithm).
But are there better algorithms for other values of $k$?
Solution
$k$-SUM can be solved more quickly as follows.
-
For even $k$: Compute a sorted list $S$ of all sums of $k/2$ input elements. Check whether $S$ contains both some number $x$ and its negation $-x$. The algorithm runs in $O(n^{k/2}\log n)$ time.
-
For odd $k$: Compute the sorted list $S$ of all sums of $(k-1)/2$ input elements. For each input element $a$, check whether $S$ contains both $x$ and $-a-x$, for some number $x$. (The second step is essentially the $O(n^2)$-time algorithm for 3SUM.) The algorithm runs in $O(n^{(k+1)/2})$ time.
Both algorithms are optimal (except possibly for the log factor when $k$ is even and bigger than $2$) for any constant $k$ in a certain weak but natural restriction of the linear decision tree model of computation. For more details, see:
-
Nir Ailon and Bernard Chazelle. Lower bounds for linear degeneracy testing. JACM 2005.
-
Jeff Erickson. Lower bounds for linear satisfiability problems. CJTCS 1999.
-
For even $k$: Compute a sorted list $S$ of all sums of $k/2$ input elements. Check whether $S$ contains both some number $x$ and its negation $-x$. The algorithm runs in $O(n^{k/2}\log n)$ time.
-
For odd $k$: Compute the sorted list $S$ of all sums of $(k-1)/2$ input elements. For each input element $a$, check whether $S$ contains both $x$ and $-a-x$, for some number $x$. (The second step is essentially the $O(n^2)$-time algorithm for 3SUM.) The algorithm runs in $O(n^{(k+1)/2})$ time.
Both algorithms are optimal (except possibly for the log factor when $k$ is even and bigger than $2$) for any constant $k$ in a certain weak but natural restriction of the linear decision tree model of computation. For more details, see:
-
Nir Ailon and Bernard Chazelle. Lower bounds for linear degeneracy testing. JACM 2005.
-
Jeff Erickson. Lower bounds for linear satisfiability problems. CJTCS 1999.
Context
StackExchange Computer Science Q#2973, answer score: 37
Revisions (0)
No revisions yet.