Tight bounds for online vector bin packing

DOI10.1145/2488608.2488730zbMath1293.90053OpenAlexW2053641648MaRDI QIDQ5495868

Bruce Shepherd, Seny Kamara, Ilan Reuven Cohen, Yossi Azar

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2488608.2488730

zbMATH Keywords

online algorithmscompetitive ratiolower boundsbin packingvector packinggraph-coloring

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Online bin packing with cardinality constraints resolved ⋮ Online two-dimensional vector packing with advice ⋮ Lower Bounds for On-line Interval Coloring with Vector and Cardinality Constraints ⋮ Tight Bounds for Online Vector Scheduling ⋮ Online bin packing of squares and cubes ⋮ Online packing of arbitrary sized items into designated and multipurpose bins ⋮ Online bin packing of squares and cubes ⋮ Unnamed Item ⋮ Streaming algorithms for bin packing and vector scheduling ⋮ Online Submodular Maximization Problem with Vector Packing Constraint.

This page was built for publication: Tight bounds for online vector bin packing