Optimal online k-min search
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 a...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Elsevier
2015
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/3f9eb8d0419d47439ca1701b96211a34 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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. |
|---|