A Comparison of Performance Measures via Online Search.

Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
Theoretical Computer Science, 532: 2-13, 2014.

Since the introduction of competitive analysis, a number of alternative measures for the quality of online algorithms have been proposed, but, with a few exceptions, these have generally been applied only to the online problem for which they were developed. Recently, a systematic study of performance measures for online algorithms was initiated [Boyar, Irani, Larsen: Eleventh International Algorithms and Data Structures Symposium 2009], first focusing on a simple server problem. We continue this work by studying a fundamentally different online problem, online search, and the Reservation Price Policies in particular. The purpose of this line of work is to learn more about the applicability of various performance measures in different situations and the properties that the different measures emphasize. We investigate the following analysis techniques: Competitive, Relative Worst Order, Bijective, Average, Relative Interval, Random Order, and Max/Max. In addition, we have established the first optimality proof for Relative Interval Analysis.

---

publication

Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any): The publication is available from ScienceDirect.

open access (206 KB)

The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.

other publications

Other publications by the author.