Online Algorithms with Advice for the -search Problem

• Main Authors: Clemente, Jhoirene B, Adorna, Henry N, Fernandez, Proceso L, Jr
• Format: text
• Published: Archīum Ateneo 2022
• Subjects: advice complexity; competitive analysis; online algorithms; online search; Applied Mathematics; Mathematics; Physical Sciences and Mathematics
• Online Access: https://archium.ateneo.edu/discs-faculty-pubs/343; https://archium.ateneo.edu/cgi/viewcontent.cgi?article=1343&context=discs-faculty-pubs
• Institution: Ateneo De Manila University

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 and compute the performance guarantee. Although it is natural to expect improvement due to the additional power of advice, we are interested to identify the relationship of additional information with respect to the improvement. We show that with 1 bit of advice, we can already surpass the quality of the best possible deterministic algorithm for online 2-search. We also provide a set of online algorithms, ALGί, that utilizes [Formula Presented] advice bits with a competitive ratio of (formula presented). We show that increasing the amount of advice improves the solution quality of the algorithm. Moreover, we compare the power of advice and randomization. We show that for some identified minimum number of advice bits, the lower bound on the competitive ratio of online algorithms with advice is better than any deterministic and randomized algorithm for online k-search.