Online Two Stage k-Search Problem and Its Competitive Analysis
Wenming Zhang, E. Zhang, Feifeng Zheng · International Journal of Foundations of Computer Science · 2016
This work investigates an online two stage k-search problem where an online player makes selections in two stages. In the first stage a number of more than k quoted prices are selected as candidates, and then exactly k highest quoted prices are chosen from the candidates in the second stage. The objective is to maximize the total profit of the k final accepted prices. We mainly propose a deterministic online algorithm and prove that it is optimal in competitiveness. A further discussion is given considering various relationships between the value of k and the number of candidates.