Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Entire DC Network
Online Algorithms With Advice For The š-Search Problem, Jhoirene B. Clemente, Henry N. Adorna, Proceso L. Fernandez Jr
Online Algorithms With Advice For The š-Search Problem, Jhoirene B. Clemente, Henry N. Adorna, Proceso L. Fernandez Jr
Department of Information Systems & Computer Science Faculty Publications
In the online search problem, a seller seeks to find the maximum price from a sequence of prices p1, p2,ā¦, pn that is revealed in a piece-wise manner. The bound for all prices is well known in advance with m ā¤ pĪÆ ā¤ M. In the online k-search problem, the seller seeks to find the k maximum out of the n prices. In this paper, we present a tight bound of [Formula Presented] on the advice complexity of optimal online algorithms for online k-search. We also provide online algorithms with advice that use less than the required number of bits ā¦