Brief Announcement: Tight bounds for Dynamic Bin Packing with Predictions

被引：1
|
作者：
Liu, Mozhengfu [1 ]
Tang, Xueyan [2 ]
机构：
[1] Northwestern Univ, Evanston, IL 60201 USA
[2] Nanyang Technol Univ, Singapore, Singapore
来源：
PROCEEDINGS OF THE 36TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2024 | 2024年
关键词：
dynamic bin packing; busy time; scheduling; algorithms with predictions; competitive ratio; consistency; robustness;
D O I：
10.1145/3626183.3660271
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
MinUsageTime DBP is a variant of the Dynamic Bin Packing (DBP) problem that seeks to minimize the accumulated length of time for which bins are used in packing a sequence of items. This paper studies the MinUsageTime DBP problem with predictions about item durations. We establish tight competitiveness bounds over the entire spectrum of prediction errors.
引用
收藏
页码：297 / 299
页数：3
相关论文
共 50 条
  • [1] Tight Bounds for Dynamic Bin Packing with Predictions
    Li, Mozhengfu
    Tang, Xuevan
    PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS, 2024, 8 (03)
  • [2] Tight Bounds for Clairvoyant Dynamic Bin Packing
    Azar, Yossi
    Vainstein, Danny
    PROCEEDINGS OF THE 29TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA'17), 2017, : 77 - 86
  • [3] Tight Bounds for Clairvoyant Dynamic Bin Packing
    Azar, Yossi
    Vainstein, Danny
    ACM TRANSACTIONS ON PARALLEL COMPUTING, 2019, 6 (03)
  • [4] Dynamic Bin Packing with Predictions
    Liu, Mozhengfu
    Tang, Xueyan
    PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS, 2022, 6 (03)
  • [5] Tight Bounds for Online Vector Bin Packing
    Azar, Yossi
    Cohen, Ilan
    Kamara, Seny
    Shepherd, Bruce
    STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2013, : 961 - 970
  • [6] Brief Announcement: Dynamic Vector Bin Packing for Online Resource Allocation in the Cloud
    Murhekar, Aniket
    Arbour, David
    Mai, Tung
    Rao, Anup
    PROCEEDINGS OF THE 35TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2023, 2023, : 307 - 310
  • [7] Brief Announcement: Tight Space Bounds for Memoryless Anonymous Consensus
    Zhu, Leqi
    DISTRIBUTED COMPUTING (DISC 2015), 2015, 9363 : 665 - 666
  • [8] Brief Announcement: Tight Bounds for Repeated Balls-into-Bins
    Los, Dimitrios
    Sauerwald, Thomas
    PROCEEDINGS OF THE 34TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2022, 2022, : 419 - 421
  • [9] Online Bin Packing with Predictions
    Angelopoulos, Spyros
    Kamali, Shahin
    Shadkami, Kimia
    JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2023, 78 : 1111 - 1141
  • [10] Online Bin Packing with Predictions
    Angelopoulos S.
    Kamali S.
    Shadkami K.
    Journal of Artificial Intelligence Research, 2023, 78 : 1111 - 1141
12345