TY - GEN
T1 - A Comparison of Performance Measures via Online Search
AU - Boyar, Joan
AU - Larsen, Kim Skak
AU - Maiti, Abyayananda
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
KW - online search
KW - quality measures for online algorithms
U2 - 10.1007/978-3-642-29700-7_28
DO - 10.1007/978-3-642-29700-7_28
M3 - Article in proceedings
SN - 978-3-642-29699-4
VL - 7285
T3 - Lecture Notes in Computer Science
SP - 303
EP - 314
BT - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
T2 - Frontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference
Y2 - 14 May 2012 through 16 May 2012
ER -