Online binary minimax trees

In the binary minimax tree problem we are given non-negative weights W=(w1,…,wn)W=(w1,…,wn). The task is to find a rooted binary tree TT with nn leaves and an assignment of the leaves to the weights such that the maximum over all leaves ll of the weight of ll plus the depth of ll is minimized.We present an online algorithm for building an optimal binary minimax tree with integral weights that runs in O(nlogn/loglogn) time using exponential search trees. Moreover, we show that no online algorithm computing an optimal minimax tree exists if we allow non-integral real weights.