Rina Atsumi

dblp:415/4700 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
2since 2021 · last 2026
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 2 since 2021
YearPublicationVenuePosition
2026 Max-min and 1-bounded space algorithms for the bin packing problem
abstract
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.
Hiroshi Fujiwara, Rina Atsumi, Hiroaki Yamamoto
Theor. Comput. Sci.2
2025 Max-Min and 1-Bounded Space Algorithms for the Bin Packing Problem
Hiroshi Fujiwara, Rina Atsumi, Hiroaki Yamamoto
WAOA2