Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908551427915776 |
|---|---|
| author | Fujiwara, Hiroshi Atsumi, Rina Yamamoto, Hiroaki |
| author_facet | Fujiwara, Hiroshi Atsumi, Rina Yamamoto, Hiroaki |
| contents | In the (1-dimensional) bin packing problem, we are asked to pack all the given items into bins, each of capacity one, so that the number of non-empty bins is minimized. Zhu~[Chaos, Solitons \& Fractals 2016] proposed an approximation algorithm $MM$ that sorts the item sequence in a non-increasing order by size at the beginning, and then repeatedly packs, into the current single open bin, first as many of the largest items in the remaining sequence as possible and then as many of the smallest items in the remaining sequence as possible. In this paper we prove that the asymptotic approximation ratio of $MM$ is at most 1.5. Next, focusing on the fact that $MM$ is at the intersection of two algorithm classes, max-min algorithms and 1-bounded space algorithms, we comprehensively analyze the theoretical performance bounds of each subclass derived from the two classes. Our results include a lower bound of 1.25 for the intersection of the two classes. Furthermore, we extend the theoretical analysis over algorithm classes to the cardinality constrained bin packing problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_18718 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem Fujiwara, Hiroshi Atsumi, Rina Yamamoto, Hiroaki Data Structures and Algorithms Discrete Mathematics Combinatorics Optimization and Control In the (1-dimensional) bin packing problem, we are asked to pack all the given items into bins, each of capacity one, so that the number of non-empty bins is minimized. Zhu~[Chaos, Solitons \& Fractals 2016] proposed an approximation algorithm $MM$ that sorts the item sequence in a non-increasing order by size at the beginning, and then repeatedly packs, into the current single open bin, first as many of the largest items in the remaining sequence as possible and then as many of the smallest items in the remaining sequence as possible. In this paper we prove that the asymptotic approximation ratio of $MM$ is at most 1.5. Next, focusing on the fact that $MM$ is at the intersection of two algorithm classes, max-min algorithms and 1-bounded space algorithms, we comprehensively analyze the theoretical performance bounds of each subclass derived from the two classes. Our results include a lower bound of 1.25 for the intersection of the two classes. Furthermore, we extend the theoretical analysis over algorithm classes to the cardinality constrained bin packing problem. |
| title | Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem |
| topic | Data Structures and Algorithms Discrete Mathematics Combinatorics Optimization and Control |
| url | https://arxiv.org/abs/2508.18718 |