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...