Given $n$ tuples $(k_i >0,a_i >0)$, is there any efficient algorithm that can dynamically track $$ \max_{i=1,\cdots,n} \left\{k_i\left(\sum_{j=1}^n a_j\right) - a_i\right\} $$ in response to online updates to $a_i$? (in $\text{poly}(\log n)$ complexity per update).

I do have an algorithm in mind, which sees $k_i$s as the slope of lines and $-a_i$s as intercepts. The problem then can be reduced to maintaining the upper envelope of $n$ lines, which can be further reduced to a dynamic planar convex hull problem with established algorithm giving $\mathcal O(\log^2n)$ worst-case complexity per update.

I am not satisfied by my reduction because it ignores many specific structure of the problem that may be exploited. In addition, because I need to actually implement this algorithm in my project, a solution with dynamic convex hull is just way too tedious. Are there simpler algorithms for this problem with comparable complexity?

  • $\begingroup$ what is the desired space complexity? $\endgroup$ Sep 11 at 6:52
  • $\begingroup$ @InuyashaYagami I expect $n$ to be on the order of $10^5$ to $10^6$ so a space complexity of $\mathcal O(n \log n)$ or $\mathcal O(n \log^2 n)$ would be reasonable. $\mathcal O(n \sqrt n)$ would be acceptable too if that's necessary. $\endgroup$ Sep 11 at 12:58

Your Answer

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

Browse other questions tagged or ask your own question.