A Comparison of Performance Measures via Online Search

Joan Boyar, Kim Skak Larsen, Abyayananda Maiti

Research output: Contribution to journalConference articleResearchpeer-review

Abstract

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.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Volume7285
Pages (from-to)303-314
Number of pages12
ISSN0302-9743
DOIs
Publication statusPublished - 2012
EventFrontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference - Beijing, China
Duration: 14. May 201216. May 2012

Conference

ConferenceFrontiers in Algorithmics and Algorithmic Aspects in Information and Management - Joint International Conference
CountryChina
CityBeijing
Period14/05/201216/05/2012

Fingerprint

Performance Measures
Online Algorithms
Competitive Analysis
Interval Analysis
Servers
Reservation
Bijective
Exception
Optimality
Continue
Server
Interval
Line
Alternatives
Policy

Cite this

@inproceedings{e0c1f5b04c7a4c93805095e19b279a77,
title = "A Comparison of Performance Measures via Online Search",
abstract = "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.",
keywords = "online search, quality measures for online algorithms",
author = "Joan Boyar and Larsen, {Kim Skak} and Abyayananda Maiti",
year = "2012",
doi = "10.1007/978-3-642-29700-7_28",
language = "English",
volume = "7285",
pages = "303--314",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Heinemann",

}

A Comparison of Performance Measures via Online Search. / Boyar, Joan; Larsen, Kim Skak; Maiti, Abyayananda.

In: Lecture Notes in Computer Science, Vol. 7285, 2012, p. 303-314.

Research output: Contribution to journalConference articleResearchpeer-review

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 - Conference article

VL - 7285

SP - 303

EP - 314

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -