- A Comparison of Performance Measures via Online Search.
- Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
In Joint International Conference on Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM), volume 7285 of Lecture Notes in Computer Science, pages 303-314. Springer, 2012.
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
Recently, a systematic study of performance measures for online
algorithms was initiated
[Boyar, Irani, Larsen: WADS 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, and Random Order.
In addition, we have established the
first optimality proof for Relative Interval Analysis.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
Other publications by the author.