Yossi Azar
ABSTRACT
In the d-dimensional bin packing problem (VBP), one is given vectors x1,x2, ... ,xn ∈ Rd and the goal is to find a partition into a minimum number of feasible sets: {1,2 ... ,n} = ∪is Bi. A set Bi is feasible if ∑j ∈ Bi xj ≤ 1, where 1 denotes the all 1's vector. For online VBP, it has been outstanding for almost 20 years to clarify the gap between the best lower bound Ω(1) on the competitive ratio versus the best upper bound of O(d). We settle this by describing a Ω(d1-ε) lower bound. We also give strong lower bounds (of Ω(d1/B-ε) ) if the bin size B ∈ Z+ is allowed to grow. Finally, we discuss almost-matching upper bound results for general values of B; we show an upper bound whose exponent is additively "shifted by 1" from the lower bound exponent.
- N. Buchbinder and J. Naor. Online primal-dual algorithms for covering and packing problems. 13th Annual European Symposium on Algorithms - ESA 2005, 2005. Google Scholar
Digital Library
- C. Chekuri and S. Khanna. On multi-dimensional packing problems. SIAM journal on computing, 33(4):837--851, 2004. Google ScholarDigital Library
- E.G. Coffman Jr, M.R. Garey, and D.S. Johnson. Approximation algorithms for bin packing: A survey. In Approximation algorithms for NP-hard problems, pages 46--93. PWS Publishing Co., 1996. Google ScholarDigital Library
- J. Csirik and G. Woeginger. On-line packing and covering problems. Online Algorithms, pages 147--177, 1998. Google ScholarDigital Library
- B.C. Dean, M.X. Goemans, and J. Vondrák. Adaptivity and approximation for stochastic packing problems. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 395--404. Society for Industrial and Applied Mathematics, 2005. Google ScholarDigital Library
- B.C. Dean, M.X. Goemans, and J. Vondrák. Approximating the stochastic knapsack problem: The benefit of adaptivity. Mathematics of Operations Research, 33(4):945--964, 2008.Google ScholarCross Ref
- L. Epstein. On variable sized vector packing. Acta Cybernetica, 16(1):47--56, 2003. Google ScholarDigital Library
- D.K. Friesen and M.A. Langston. Variable sized bin packing. SIAM journal on computing, 15:222, 1986. Google ScholarDigital Library
- G. Galambos, H. Kellerer, and G.J. Woeginger. A lower bound for on-line vector-packing algorithms. Acta Cybernetica, 11(1--2):23--34, 1993.Google Scholar
- G. Galambos and G.J. Woeginger. On-line bin packing - a restricted survey. Mathematical Methods of Operations Research, 42(1):25--45, 1995.Google ScholarCross Ref
- MR Garey, RL Graham, DS Johnson, and A.C.C. Yao. Resource constrained scheduling as generalized bin packing. Journal of Combinatorial Theory, Series A, 21(3):257--298, 1976.Google ScholarCross Ref
- A. Gyárfás and J. Lehel. On-line and first fit colorings of graphs. Journal of Graph Theory, 12(2):217--227, 1988.Google ScholarCross Ref
- M.M. Halldórsson. Online coloring known graphs. In Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, pages 917--918. Society for Industrial and Applied Mathematics, 1999. Google ScholarDigital Library
- M.M. Halldórsson and M. Szegedy. Lower bounds for on-line graph coloring. In Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, pages 211--216. Society for Industrial and Applied Mathematics, 1992. Google ScholarDigital Library
- S. Irani. Coloring inductive graphs on-line. Algorithmica, 11(1):53--72, 1994.Google ScholarDigital Library
- H. Kierstead. On-line coloring k-colorable graphs. Israel Journal of Math, 105:93--104, 1998.Google ScholarCross Ref
- L. Lovasz, M. Saks, and WT Trotter. An on-line graph coloring algorithm with sublinear performance ratio. DISCRETE MATH., 75(1):319--325, 1989. Google ScholarDigital Library
- R. Panigrahy, K. Talwar, L. Uyeda, and U. Wieder. Heuristics for vector bin packing.Google Scholar
- S.S. Seiden, R. Van Stee, and L. Epstein. New bounds for variable-sized online bin packing. SIAM Journal on Computing, 32(2):455--469, 2003. Google ScholarDigital Library
- S. Vishwanathan. Randomized online graph coloring. Journal of algorithms, 13(4):657--669, 1992.Google ScholarCross Ref
- A.C.C. Yao. Probabilistic computations: Toward a unified measure of complexity. In 18th Annual Symposium on Foundations of Computer Science, pages 222--227. IEEE, 1977. Google ScholarDigital Library
- Y.O. Yazir, C. Matthews, R. Farahbod, S. Neville, A. Guitouni, S. Ganti, and Y. Coady. Dynamic resource allocation in computing clouds using distributed multiple criteria decision analysis. In Cloud Computing (CLOUD), 2010 IEEE 3rd International Conference on, pages 91--98. Ieee, 2010. Google ScholarDigital Library
- Q. Zhang, L. Cheng, and R. Boutaba. Cloud computing: state-of-the-art and research challenges. Journal of Internet Services and Applications, 1(1):7--18, 2010.Google ScholarCross Ref
Index Terms
- Tight bounds for online vector bin packing
Recommendations
Tight bounds for online class-constrained packing
Latin American theorotical informaticsWe consider class-constrained packing problems, in which we are given a set of bins, each having a capacity v and c compartments, and n items of M different classes and the same (unit) size. We need to fill the bins with items, subject to capacity ...
Online Results for Black and White Bin Packing
In online bin packing problems, items of sizes in [0, 1] are to be partitioned into subsets of total size at most 1, called bins. We introduce a new variant where items are of two types, called black and white, and the item types must alternate in each ...
New Bounds for Multidimensional Packing
New upper and lower bounds are presented for a multidimensional generalization of bin packing called box packing. Several variants of this problem, including bounded space box packing, square packing, variable-sized box packing and resource augmented ...
Comments