Comparing online algorithms for bin packing problems

被引：21
|
作者：
Epstein, Leah [1 ]
Favrholdt, Lene M. [2 ]
Kohrt, Jens S. [2 ]
机构：
[1] Univ Haifa, Dept Math, IL-31999 Haifa, Israel
[2] Univ So Denmark, Dept Math & Comp Sci, Odense, Denmark
来源：
JOURNAL OF SCHEDULING | 2012年 / 15卷 / 01期
关键词：
Online algorithms; Relative worst-order ratio; Bin packing; Bin covering; Bin coloring; Class-constrained bin packing; Open-end bin packing; WORST-ORDER RATIO; DUAL VERSION; BOUNDS;
D O I：
10.1007/s10951-009-0129-5
中图分类号：
T [工业技术];
学科分类号：
08 ;
摘要：
The relative worst-order ratio is a measure of the quality of online algorithms. In contrast to the competitive ratio, this measure compares two online algorithms directly instead of using an intermediate comparison with an optimal offline algorithm. In this paper, we apply the relative worst-order ratio to online algorithms for several common variants of the bin packing problem. We mainly consider pairs of algorithms that are not distinguished by the competitive ratio and show that the relative worst-order ratio prefers the intuitively better algorithm of each pair.
引用
收藏
页码：13 / 21
页数：9
相关论文
共 50 条
  • [1] Comparing online algorithms for bin packing problems
    Leah Epstein
    Lene M. Favrholdt
    Jens S. Kohrt
    Journal of Scheduling, 2012, 15 : 13 - 21
  • [2] Online algorithms with advice for bin packing and scheduling problems
    Renault, Marc P.
    Rosen, Adi
    van Stee, Rob
    THEORETICAL COMPUTER SCIENCE, 2015, 600 : 155 - 170
  • [3] Parallel Online Algorithms for the Bin Packing Problem
    Fekete, Sandor P.
    Grosse-Holz, Jonas
    Keldenich, Phillip
    Schmidt, Arne
    ALGORITHMICA, 2023, 85 (01) : 296 - 323
  • [4] Parallel Online Algorithms for the Bin Packing Problem
    Fekete, Sandor P.
    Grosse-Holz, Jonas
    Keldenich, Phillip
    Schmidt, Arne
    APPROXIMATION AND ONLINE ALGORITHMS (WAOA 2019), 2020, 11926 : 106 - 119
  • [5] ONLINE ALGORITHMS FOR A DUAL VERSION OF BIN PACKING
    CSIRIK, J
    TOTIK, V
    DISCRETE APPLIED MATHEMATICS, 1988, 21 (02) : 163 - 167
  • [6] Parallel Online Algorithms for the Bin Packing Problem
    Sándor P. Fekete
    Jonas Grosse-Holz
    Phillip Keldenich
    Arne Schmidt
    Algorithmica, 2023, 85 : 296 - 323
  • [7] Comparing the costs of Any Fit algorithms for bin packing
    Levin, Asaf
    OPERATIONS RESEARCH LETTERS, 2022, 50 (06) : 646 - 649
  • [8] Online algorithms with advice for the dual bin packing problem
    Marc P. Renault
    Central European Journal of Operations Research, 2017, 25 : 953 - 966
  • [9] Algorithms for the relaxed online bin-packing model
    Gambosi, G
    Postiglione, A
    Talamo, M
    SIAM JOURNAL ON COMPUTING, 2000, 30 (05) : 1532 - 1551
  • [10] Approximation and online algorithms for multidimensional bin packing: A survey
    Christensen, Henrik I.
    Khan, Arindam
    Pokutta, Sebastian
    Tetali, Prasad
    COMPUTER SCIENCE REVIEW, 2017, 24 : 63 - 79
12345