The Weighted k-Search Problem

In the uni-directional conversion problem, the objective is to convert wealth from one asset into another while maximizing its value at the end of the investment horizon. In the k-preemptive variant of this problem, also known as the k-search problem, the wealth is divided into k equally-sized units that cannot be converted simultaneously. In this work the weighted k-search problem is introduced. The weighted k-search problem is a generalization of the k-search problem, since the problem setting is changed in a way in which the given number of units to convert is not limited to one. In the weighted k-search problem, the k units are grouped into l groups of variable size. Instead of one unit, each group has to be converted at once, and each group has to be converted separately. The online algorithm lRPP is presented and its competitive ratio is determined. It is shown that no deterministic algorithm can achieve a lower competitive ratio. Thus, lRPP solves the weighted k-search problem optimally. Both variants of the weighted k-search problem, i.e., min-search and max-search, are solved separately.