Online-bounded analysis

Joan Boyar (), Leah Epstein (), Lene M. Favrholdt (), Kim S. Larsen () and Asaf Levin ()
Additional contact information
Joan Boyar: University of Southern Denmark
Leah Epstein: University of Haifa
Lene M. Favrholdt: University of Southern Denmark
Kim S. Larsen: University of Southern Denmark
Asaf Levin: The Technion

Journal of Scheduling, 2018, vol. 21, issue 4, No 3, 429-441

Abstract: Abstract Though competitive analysis is often a very good tool for the analysis of online algorithms, sometimes it does not give any insight and sometimes it gives counter-intuitive results. Much work has gone into exploring other performance measures, in particular targeted at what seems to be the core problem with competitive analysis: The comparison of the performance of an online algorithm is made with respect to a too powerful adversary. We consider a new approach to restricting the power of the adversary, by requiring that when judging a given online algorithm, the optimal offline algorithm must perform at least as well as the online algorithm, not just on the entire final request sequence, but also on any prefix of that sequence. This is limiting the adversary’s usual advantage of being able to exploit that it knows the sequence is continuing beyond the current request. Through a collection of online problems, including machine scheduling, bin packing, dual bin packing, and seat reservation, we investigate the significance of this particular offline advantage.

Keywords: Online algorithms; Quality measures; Machine scheduling; Bin packing (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-017-0536-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:21:y:2018:i:4:d:10.1007_s10951-017-0536-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-017-0536-y

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().