patternMinor
Given n sorted arrays with size k select one element from every array such that the sum of the elements is minimum and the sum of their indices is k+1
Viewed 0 times
arrayeveryminimumelementindiceselementsonethatsumselect
Problem
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.
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.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#118842, answer score: 2
Revisions (0)
No revisions yet.