Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given positive integers $L$ and a set of non-negative integers $N$.

Find maximum of: $$\large \sum_{i = 1}^{4L}\ N_i\cdot(\min(\vert i - c\vert, 4L - \vert i - c\vert))$$

with $c \in \{1, 2,\dots ,4L\}$ and $\frac {\text {number of } N_i > 0} {L}$ is small (about $\frac 1 {100}$)


How can I solve this and similar problems efficiently? Thanks.

share|improve this question
1  
Let me understand your problem better. What are the variables of your problem? The sum goes from 1 to $4L−1$ ? –  Adrian Schad Jun 11 at 8:14
    
I edited my question. –  Xeing Jun 11 at 11:05
    
Yes, sorry about that. –  Xeing Jun 12 at 18:28
    
You want to find $c$ that maximizes the sum? And must $c$ be an integer? –  alex.jordan Jun 12 at 18:33
1  
I can solve your problem, however only if minimization is performed instead of maximization. Does this help you? –  Adrian Schad Jun 13 at 6:40

2 Answers 2

up vote 5 down vote accepted
+25

Problem: I assume the problem is $$ \begin{align} S &= \max_{c \in \{1, \ldots, 4L\}} \sum_{i=1}^{4L} N_i \min \left(|i-c|, 4L-|i-c|\right) \\ &= \max_{c \in \{1, \ldots, 4L\}} T(c) \end{align} \quad (*) $$

Complexity Simple Search: A simple search of $(*)$ over all $c$-values would require about $(4L)^2$ term evaluations, needing 1 $+$, 1 $\cdot$, 2 $-$, 1 $\min(.,.)$ and 1 $|.|$ calculation each.

Lemma 1: The change $\Delta T$ for increasing $c$ is:

$$ \Delta T(c) := T(c+1) - T(c) $$

It can be calculated recursively:

$$ \begin{align} \Delta T(1) &:= N_1 - \sum_{i=2}^{2L+1} N_i + \sum_{i=2L+2}^{4L} N_i \\ \Delta T(c) &:= \Delta T(c-1) + 2(N_{c} - N_{2L + c}) \quad c \in \{ 2, \ldots, 2L \} \end{align} \quad (**) $$

Lemma 2: The change has a symmetry: $$ \Delta T(c) = -\Delta T(c - 2L), \quad c \in \{ 2L+1, \ldots, 4L \} $$

Thus we can calculate the $2L$ values of $\Delta T$ in the second half of the $c$-interval faster, because we can make use of the values from the first half.

Quick Summation: Calculate the relative sum vector $Q$: $$ \begin{align} Q(1) &:= 0 \\ Q(c) &:= Q(c-1) + \Delta T(c-1) \\ \end{align} \quad c \in \{ 2, \cdots, 4L \} $$

Lemma 3: The $c^*$ which maximizes $Q(c)$ will maximize $T(c)$ as well.

Solution: Determine $c^*$ according to lemma 3 and the quick summation procedure. Then calculate

$$ S = T(c^*) $$

using the original defintion $(*)$ or even better using the optimized term evaluation:

$$ \begin{align} T_{L->R}(c) &:= \sum_{i = 1}^{c-1} N_i \, (c-i) + \sum_{i = c+1}^{2L+c-1} N_i \, (i-c) + \sum_{i = 2L+c}^{4L} N_i \, (4L - (i-c)) \\ & \quad c \in \{ 1, \ldots, 2L \} \\ T_{R->L}(c) &:= \sum_{i = 1}^{c - 2L} N_i \, (4L - (c-i)) + \sum_{i = c - 2L + 1}^{c-1} N_i \, (c-i) + \sum_{i = c + 1}^{4L} N_i \, (i-c) \\ & \quad c \in \{ 2L+1, \ldots, 4L \} \end{align} \quad (\#) $$

The optimized term $(\#)$ avoids minimum and absolute value operations. Its greater benefit is that it allows to determine the differences for lemma 1.

Complexity of the Solution: The complexity relative to the simple search has been reduced to less than $16 L$ $+$, $12 L$ $-$ and $6L$ $\cdot$ operations. Or roughly from quadratic to linear. In both cases not considering the similar $4L$ comparisons for the extremum search.

Bonus Lemma 1: The same procedure works for searching the minimum sum efficiently, just replace $\max$ with $\min$.

Bonus Lemma 2: The $N_i$ can be arbitrary real numbers.

Derivation of the Optimized Terms: We can avoid the minimum calculations in $(*)$ by using $T_{L\to R}$ for the $c$-values from $1$ up to $c_s = 2L$ and then using $T_{R\to L}$. We further split those sums after $i_{s, L\to R} = 2L+c-1$ and $i_{s, R\to L} = c - 2L$:

$$ \begin{align} T_{L->R}(c) &= \sum_{i = 1}^{2L+c-1} N_i \, |i-c| + \sum_{i = 2L+c}^{4L} N_i \, (4L - (i-c)) \\ T_{R->L}(c) &= \sum_{i = 1}^{c - 2L} N_i \, (4L - (c-i)) + \sum_{i = c - 2L + 1}^{4L} N_i \, |i-c| \end{align} $$

And we can split up two sums further to avoid the decisions during absolute value calculations, getting $(i-c)$ and $(c-i)$ factors. This yields $(\#)$.

Proof Lemma 1: The change $\Delta T$ for increasing $c$ is: $$ \Delta T(c) := T(c+1) - T(c) = \sum_{i=1}^c N_i - \sum_{i=c+1}^{2L+c} N_i + \sum_{i=2L+c+1}^{4L} N_i, \quad c \in \{ 1, \ldots, 2L \} \quad (\#\#) $$ This has been derived from $(\#)$ by analyzing how that expression changes from $c$ to $c+1$. It is a discrete analogon to differentiation. The expression is simpler than $(*)$ but still contains the information to determine the optimum.

Applying this idea again: If one knows $\Delta T(c)$, one can calculate $\Delta T(c+1)$ using:

$$ \Delta^2 T(c) := \Delta T(c+1) - \Delta T(c) = 2(N_{c+1} - N_{2L+c+1}) $$

This has been derived from $(\#\#)$. The result is the recursive scheme $(**)$.

Proof Lemma 2: Start with the second branch from $(\#)$. Determine the difference like in the proof of lemma 1. Compare the result with $(\#\#)$.

Proof Lemma 3: The relative sum $Q$ differs only by a constant from $T$ $$ Q(c) = T(c) - T(1). $$

Appendix:

  • Here is a program written in Ruby, for those who want to experiment a bit more with this problem.
    Sample output here or here or here. It generates random $N$-vectors and also checks if the optimized equations $(\#)$ give the same results like the original $(*)$.
  • Observation: The changes of the sums $$ \frac{\Delta}{\Delta c} \sum\limits_{i = a(c)}^{b(c)}t(i, c) $$ seem to behave similar to the derivatives of the parameter integrals $$ \frac{\partial}{\partial c} \int\limits_{a(c)}^{b(c)} t(x, c) \, dx = t(b(c),c) \, b'(c) - t(a(c), c) \, a'(c) + \int\limits_{a(c)}^{b(c)} \!\! \frac{\partial}{\partial c} t(x, c) \, dx $$
share|improve this answer

If $c$ is an integer, it is worth noting that full search is maybe the fastest way to solve your problem. Trying out all possible values $c=1,\dots,4L$ is not critical in your case as the problem is one-dimensional.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.