A Comparison of Performance Measures via Online Search

Joan Boyar, Kim Skak Larsen, Abyayananda Maiti

Publikation: Bidrag til tidsskriftKonferenceartikelForskningpeer review

Abstrakt

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: 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.
OriginalsprogEngelsk
BogserieLecture Notes in Computer Science
Vol/bind7285
Sider (fra-til)303-314
Antal sider12
ISSN0302-9743
DOI
StatusUdgivet - 2012
BegivenhedFrontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference - Beijing, Kina
Varighed: 14. maj 201216. maj 2012

Konference

KonferenceFrontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference
Land/OmrådeKina
ByBeijing
Periode14/05/201216/05/2012

Emneord

  • online search
  • quality measures for online algorithms

Fingeraftryk

Dyk ned i forskningsemnerne om 'A Comparison of Performance Measures via Online Search'. Sammen danner de et unikt fingeraftryk.

Citationsformater