Optimal online k-min search

Abstract

In a k-min search problem, a player wants to buy k units of an asset with the objective of minimizing the total buying cost. At each time period t, a price qt is observed, and the player has to decide on the number of units to buy without any knowledge of future prices. We design an optimal online algorithm for the k-min search problem that is valid for both k≤T and k>T (T being the total number of time points/days). We perform a competitive analysis of the proposed Hybrid algorithm, and compare it with the min-search strategy by conducting experiments on real-world data. We show that Hybrid achieves a better competitive ratio, and reduces the number of transactions.

Keywords

• 68W27 Online algorithms
• 68W40 Analysis of algorithms