So if $k = 3$ and $n = 2$ and we select the element $a_1[3]$ of the first array then we have to select $a_2[1]$ from the second array. If we select the element $a_1[2]$ then also $a_2[2]$ must be selected etc.

I can think of a DP algorithm to solve that which takes $O(nk)$ time (I don't think that I need to describe it, it's fairly easy to think). But I don't know if binary search can be used to find the answer more efficiently.

This may sound like a weird problem but it's part of a DP algorithm I'm trying to figure out and so the complexity will be multiplied with $kn$ so it would be great if I found a solution with $O(k)$ complexity.

  • $\begingroup$ Do you mean $\mathcal{O}(nk^2)$ time? An $\mathcal{O}(f(n)k^{2 - \epsilon})$ algorithm for any $f : \mathbb{N} \mapsto \mathbb{N}$ for this problem would solve the well-studied min-plus convolution in $\mathcal{O}(n^{2 - \epsilon})$ time. $\endgroup$ Dec 24 '19 at 23:15
  • $\begingroup$ @AnttiRöyskö You refer to the DP algorithm? I haven't given it enough thought maybe you are right. I didn't quite understand your reasoning though. $\endgroup$
    – user113632
    Dec 24 '19 at 23:50
  • $\begingroup$ I posted the reduction as an answer. I was hesitant to do so as it doesn't really answer this question, but it is too long to be contained in a comment. $\endgroup$ Dec 25 '19 at 2:39
  • $\begingroup$ Another note is that this problem clearly cannot be solved in $\mathcal{O}(k)$, as even just the input size is $\mathcal{O}(nk)$. $\endgroup$ Dec 25 '19 at 2:40
  • $\begingroup$ @Antti The input size does not necessarily imply an $\Omega(nk)$ lower bound, because the input arrays are sorted, so you don't necessarily have to read every input element. However, you do presumably need to at least read some element from all $n$ input arrays. $\endgroup$ Dec 25 '19 at 6:01

A conditional lower bound based on max-plus convolution can be shown: Fix $n = 3$. If a $\mathcal{O}(k^{2 - \epsilon})$ algorithm to this problem (with fixed $n$) exists, then MAXCONV could be solved in $\mathcal{O}(n^{2 - \epsilon})$. Max-plus convolution is a reasonable hardness assumption, as it is a much-studied problem for which no $\mathcal{O}(n^{2 - \epsilon})$-algorithm is known.

For this we'll use the result that MAXCONV can be solved in $\mathcal{O}(n^{2 - \epsilon})$ iff MAXCONV UPPERBOUND can be solved in $\mathcal{O}(n^{2 - \epsilon})$ (reference: "On Problems Equivalent to (min,+)-Convolution", ICALP 2017)

To show this, first note that we may drop the requirement that the arrays are sorted. To show this, take arbitrary values $b_{i}[j]$, set $V = 2 \max_{i, j} |b_{i}[j]|$, and set $a_{i}[j] = b_{i}[j] + Vj$. Now $a_{i}[j+1] - a_{i}[j] = b_{i}[j+1] - b_{i}[j] + V \geq 0 \geq 0$, and the answer for $a$s is exactly $(k+1)V$ more than the answer for $b$s.

In a MAXCONV UPPERBOUND instance $(a[i])_{i = 0}^{n-1}, (b[i])_{i = 0}^{n-1}, (c[i])_{i = 0}^{n-1}$ we are asked if for all $k$ we have $\max_{i+j = k} a[i] + b[j] \leq c[k]$. To reduce it to our problem, set $a_{1}[j+1] = a[j]$, $a_{2}[j+1] = b[j]$ and $a_{3}[j] = -c[n-j]$. Further set $a_{1}[n+1] = a_{2}[n+1] = a_{3}[n+1] = -\infty$. Now the answer is positive if and only if at least one of the upper bounds doesn't hold: if the answer is positive, then $a_{1}[x] + a_{2}[y] + a_{3}[z] > 0$ for some $x + y + z = n+2$, hence $a[x-1] + b[y-1] > c[(x-1)+(y-1)]$ and the upper bound for $k = x+y-2$ doesn't hold. Similarly if $a[i] + b[j] > c[i+j]$, we have $a_{1}[i+1] + a_{2}[j+1] + a_{3}[n+2 - (i+1) - (j+1)] = a[i] + b[j] - c[i+j] > 0$.

  • $\begingroup$ Thanks again for taking the time to answer. I am not very familiar with the techniques that you used however I guess you convinced me that there isn't a faster solution than the one I imagined. $\endgroup$
    – user113632
    Dec 25 '19 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy