Given $n$ tuples of $(T_1, L_1), (T_2, L_2), ..., (T_n, L_n)$ of positive integers, how would I go around finding ordered indices $j_1, j_2, ..., j_n$ such that I minimize:
$$\text{Cost}(j_1, ..., j_n)=\sum_{i=1}^{n-1}T_{j_i}\left( \sum_{k=i+1}^{n}L_{j_k} \right)$$
My Attempt:
I know that I can minimize the dot product $\mathbf{a}^T\mathbf{b}$ If I sort the elements in $\mathbf{a}$ in ascending order and $\mathbf{b}$ in descending order.
I Tried expressing this cost function in the form of a dot product:
$$\text{Cost}(j_1, ..., j_n)=(T_{j_1}\quad ...\quad T_{j_n})\left(\begin{matrix} \sum_{i=2}^nL_{j_i} \\ \sum_{i=3}^n L_{j_i} \\ \vdots \\ L_{j_n} \end{matrix}\right)$$
However, I don't see how I would sort any of the vectors since they are dependent on each other. Any help?
Ok, so I've finally found the answer and I am including it here for completion.
To simplify things, I'll assume $n=4$ but this can easily simplify for other examples.
Suppose that the minimum of cost is attained with the assignment $j_1, j_2, j_3, j_4$. Now let's say you swap any of these two, say $j_2, j_3$. Then you want to always have:
$$Cost(j_1,j_2,j_3, j_4)-Cost(j_1, j_3, j_2, j_4)\leq 0$$.
If you write this out and expand it, this reduces to:
$$-T_{j_3}L_{j_2}+T_{j_2}L_{j_3}\leq 0$$
In other words, we ALWAYS want that $$\frac{T_{j_2}}{L_{j_2}}\leq \frac{T_{j_3}}{L_{j_3}}$$
And hence the idea is to sort the elements on $$\frac{T_{j_i}}{L_{j_i}}$$ in ascending order. In doing so, you're guaranteeing that in the minimum assignment, no matter how you reorder any of the indices, you'll never attain a lower minimum that this ordering.