Approximation and online algorithms for multidimensional bin packing: A survey
The DOI matches its Crossref record; 116 of the 116 references it cites were found in a registry or an index.
Abstract
The bin packing problem is a well-studied problem in combinatorial optimization. In the classical bin packing problem, we are given a list of real numbers in ( 0 , 1 ] and the goal is to place them in a minimum number of bins so that no bin holds numbers summing to more than 1. The problem is extremely important in practice and finds numerous applications in scheduling, routing and resource allocation problems. Theoretically the problem has rich connections with discrepancy theory, iterative methods, entropy rounding and has led to the development of several algorithmic techniques. In this survey we consider approximation and online algorithms for several classical generalizations of bin packing problem such as geometric bin packing, vector bin packing and various other related problems. There is also a vast literature on mathematical models and exact algorithms for bin packing. However, this survey does not address such exact algorithms. In two-dimensional geometric bin packing , we are given a collection of rectangular items to be packed into a minimum number of unit size square bins. This variant has a lot of applications in cutting stock, vehicle loading, pallet packing, memory allocation and several other logistics and robotics related problems. In d -dimensional vector bin packing , each item is a d -dimensional vector that needs to be packed into unit vector bins. This problem is of great significance in resource constrained scheduling and in recent virtual machine placement in cloud computing. We also consider several other generalizations of bin packing such as geometric knapsack, strip packing and other related problems such as vector scheduling, vector covering etc. We survey algorithms for these problems in offline and online setting, and also mention results for several important special cases. We briefly mention related techniques used in the design and analysis of these algorithms. In the end we conclude with a list of open problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Geometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431
(2011) · SpringerReference · doi:10.1007/springerreference_57547 · Cited by 3,190
Approximation Algorithms for NP-Hard Problems
(1997) · ACM SIGACT News · doi:10.1145/261342.571216 · Cited by 3,103 · cited 2×
“For detailed introduction to approximation algorithms, we refer the readers to the following books on approximation algorithms [29,30,11,9].”
BackgroundMethodOnline Computation and Competitive Analysis
Borodin, A., & El‐Yaniv, R. (1998) · Cited by 2,333
A Linear Programming Approach to the Cutting-Stock Problem
Gilmore, P. C., & Gomory, R. E. (1961) · Operations Research · doi:10.1287/opre.9.6.849 · Cited by 2,024
Bounds for Certain Multiprocessing Anomalies
Graham, R. L. (1966) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1966.tb01709.x · Cited by 1,647 · cited 4×
“Soon in 1972, Garey, Graham and Ullman [5], provided more detailed analysis of four heuristics: FirstFit , BestFit , FirstFitDecreasing (FFD) and BestFitDecreasing (BFD).”
MethodInfluentialThe Design of Approximation Algorithms
Williamson, D. P., & Shmoys, D. B. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511921735 · Cited by 1,301 · cited 3×
“For detailed introduction to approximation algorithms, we refer the readers to the following books on approximation algorithms [29,30,11,9].”
BackgroundMethodFast Approximation Algorithms for the Knapsack and Sum of Subset Problems
Ibarra, O. H., & Kim, C. E. (1975) · Journal of the ACM · doi:10.1145/321906.321909 · Cited by 959 · cited 11×
“Ω ( d 1 − ε ) [167] Vector scheduling Offline ( d = 1) EPTAS [180] No FPTAS [177] Online ( d = 1) 1.9201 [195] 1.880 [196] Offline (constant d ) PTAS [160] No EPTAS [186] Offline (arbitrary d ) O ( log d loglog d ) [187,199] ω( 1 ) [160] Online O ( log d loglog d ) [199] Ω ( log d loglog d ) [199] Vector knapsack Offl…”
BackgroundInfluentialWorst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
Johnson, D. S., Demers, A., Ullman, J. D., Garey, M. R., & Graham, R. L. (1974) · SIAM Journal on Computing · doi:10.1137/0203025 · Cited by 911 · cited 5×
“Soon in 1972, Garey, Graham and Ullman [5], provided more detailed analysis of four heuristics: FirstFit , BestFit , FirstFitDecreasing (FFD) and BestFitDecreasing (BFD).”
BackgroundInfluentialTwo-dimensional packing problems: A survey
Lodi, A., Martello, S., & Monaci, M. (2002) · European Journal of Operational Research · doi:10.1016/s0377-2217(02)00123-6 · Cited by 843 · cited 2×
“We refer readers to [27] for a review of several greedy heuristics such as NextFitDecreasing, FirstFitDecreasing, BestFitDecreasing,”
BackgroundMethodUsing dual approximation algorithms for scheduling problems theoretical and practical results
Hochbaum, D. S., & Shmoys, D. B. (1987) · Journal of the ACM · doi:10.1145/7531.7535 · Cited by 790 · cited 3×
“Although LP (1) has an exponential number of variables, one can compute a basic solution x with 1 T x ≤ Opt f + δ in time polynomial in n and 1 /δ using the Grötschel–Lovász–Schrijver variant of the Ellipsoid method [44] or thePlotkin–Shmoys–Tardosframework[45,46].”
BackgroundInfluentialOrthogonal Packings in Two Dimensions
Baker, B. S., Coffman, Jr., & Rivest, R. L. (1980) · SIAM Journal on Computing · doi:10.1137/0209064 · Cited by 700 · cited 2×
“[25] introduced the problem in 1980 and gave an algorithm with absolute approximation ratio of 3.”
BackgroundKorte, B., & Vygen, J. (2000) · Algorithms and Combinatorics · doi:10.1007/978-3-662-21708-5_16 · Cited by 579
Near-optimal bin packing algorithms
Johnson, D. S. (1973) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 573
Fast Approximation Algorithms for Fractional Packing and Covering Problems
Plotkin, S. A., Shmoys, D. B., & Tardos, É. (1995) · Mathematics of Operations Research · doi:10.1287/moor.20.2.257 · Cited by 542
Bin packing can be solved within 1 + ε in linear time
de la Véga, W. F., & Lueker, G. S. (1981) · COMBINATORICA · doi:10.1007/bf02579456 · Cited by 510
Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
Coffman, E. G., Garey, M. R., Johnson, D. S., & Tarjan, R. E. (1980) · SIAM Journal on Computing · doi:10.1137/0209062 · Cited by 495 · cited 10×
“Many classical heuristics for 2-D strip packing [26,129,130] and 2-D GBP [89], including NFDH”
BackgroundMethodInfluentialAn efficient approximation scheme for the one-dimensional bin-packing problem
Karmarkar, N. K., & Karp, R. M. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.61 · Cited by 491 · cited 10×
“TheresultwassubstantiallyimprovedbyKarmarkarand Karp [28] who gave a guarantee of Opt + O ( log 2 Opt ) by providing an iterative rounding for a linear programming formulation.”
BackgroundMethodInfluentialFast Approximation Algorithms for Knapsack Problems
Lawler, E. L. (1979) · Mathematics of Operations Research · doi:10.1287/moor.4.4.339 · Cited by 411
A simple on-line bin-packing algorithm
Lee, C. C., & Lee, D. T. (1985) · Journal of the ACM · doi:10.1145/3828.3833 · Cited by 357 · cited 8×
“It is shown in [56] that the asymptotic approximation ratio of harmonick is Tk = m(k) q=1 1 tq + 1 tm(k)+1 · k k−1 .”
BackgroundMethodInfluentialResource constrained scheduling as generalized bin packing
Garey, M. R., Graham, R. L., Johnson, D. S., & Yao, A. C.-C. (1976) · Journal of Combinatorial Theory Series A · doi:10.1016/0097-3165(76)90001-7 · Cited by 353 · cited 1×
“A generalization of the FirstFit algorithm by Garey et al. [164] gives d + competitive ratio for the online version.”
MethodOn-line routing of virtual circuits with applications to load balancing and machine scheduling
Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., & Waarts, O. (1997) · Journal of the ACM · doi:10.1145/258128.258201 · Cited by 330 · cited 1×
“[197] obtained competitive ratio of O(logm) for makespan minimization.”
BackgroundOn the online bin packing problem
Seiden, S. S. (2002) · Journal of the ACM · doi:10.1145/585265.585269 · Cited by 310 · cited 1×
“58889) [58].”
Handbook of Combinatorial Optimization
Pardalos, P. M., Du, D., & Graham, R. L. (2013) · Springer eBooks · doi:10.1007/978-1-4419-7997-1 · Cited by 294
Handbook of Combinatorial Optimization: Volume1–3
(1998) · Springer eBooks · doi:10.1007/978-1-4613-0303-9 · Cited by 292
Bin Packing Approximation Algorithms: Survey and Classification
Coffman, E. G., Csirik, J., Galambos, G., Martello, S., & Vigo, D. (2013) · Handbook of Combinatorial Optimization · doi:10.1007/978-1-4419-7997-1_35 · Cited by 289 · cited 6×
“It is defined as follows: The Gilmore–Gomory LP relaxation [1] is used in [37,28,38] to obtain better approximation.”
BackgroundInfluentialNew Algorithms for Bin Packing
Yao, A. C.-C. (1980) · Journal of the ACM · doi:10.1145/322186.322187 · Cited by 281 · cited 1×
“Yao [161] showed that no algorithm running in time o(n log n) can give better than a dapproximation.”
BackgroundApproximation algorithms for combinatorial problems
Johnson, D. S. (1973) · Proceedings of the fifth annual ACM symposium on Theory of computing - STOC '73 · doi:10.1145/800125.804034 · Cited by 272 · cited 1×
“Johnson [10] in an influential and prescient paper in 1973 where he studied algorithms for bin packing and other packing and covering related optimization problems.”
BackgroundAlbers, S. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0436-0 · Cited by 259
Better Bounds for Online Scheduling
Albers, S. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539797324874 · Cited by 239
On Packing Two-Dimensional Bins
Chung, F., Garey, M. R., & Johnson, D. S. (1982) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0603007 · Cited by 211
New algorithms for an ancient scheduling problem
Bartal, Y., Fiat, A., Karloff, H. J., & Vohra, R. (1992) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/129712.129718 · Cited by 210 · cited 1×
“Then a series of papers [190–194] led to the present best ratio of 1.9201 [195] and the present best lower bound of 1.880 [196] for deterministic algorithms.”
BackgroundInfluentialOn Multidimensional Packing Problems
Chekuri, C., & Khanna, S. (2004) · SIAM Journal on Computing · doi:10.1137/s0097539799356265 · Cited by 208
Heuristics for Vector Bin Packing
Panigrahy, R., Talwar, K., Uyeda, L., & Wieder, U. (2011) · Cited by 203
A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
Mathieu, C., & Rémila, É. (2000) · Mathematics of Operations Research · doi:10.1287/moor.25.4.645.12118 · Cited by 203 · cited 4×
“D strip packing due to Kenyon and Rémila [90].”
BackgroundMethodInfluentialA Strip-Packing Algorithm with Absolute Performance Bound 2
Steinberg, A. M. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539793255801 · Cited by 196 · cited 5×
“Steinberg [76] provided a 2-approximation for strip packing by the following result: Theorem 2.18 ( A. Steinberg [76] ) .”
BackgroundMethodInfluentialApproximation algorithms for knapsack problems with cardinality constraints
Caprara, A., Kellerer, H., Pferschy, U., & Pisinger, D. (2000) · European Journal of Operational Research · doi:10.1016/s0377-2217(99)00261-1 · Cited by 185
An improved lower bound for on-line bin packing algorithms
van Vliet, A. (1992) · Information Processing Letters · doi:10.1016/0020-0190(92)90223-i · Cited by 183 · cited 1×
“54037 [60], improved from previous best 1.54014 [61].”
BackgroundInfluentialShelf Algorithms for Two-Dimensional Packing Problems
Baker, B. S., & Schwarz, J. S. (1983) · SIAM Journal on Computing · doi:10.1137/0212033 · Cited by 181 · cited 3×
“Baker and Schwartz [129] showed that FirstFit has asymptotic performance ratio 1.”
BackgroundInfluentialOn-line packing and covering problems
Csirik, J., & Woeginger, G. J. (1998) · Lecture notes in computer science · doi:10.1007/bfb0029568 · Cited by 181 · cited 1×
“There had been many surveys on bin packing problems thereafter [11,18, 19].”
BackgroundWorst-case analysis of memory allocation algorithms
Garey, M. R., Graham, R. L., & Ullman, J. D. (1972) · Proceedings of the fourth annual ACM symposium on Theory of computing - STOC '72 · doi:10.1145/800152.804907 · Cited by 178 · cited 1×
“Soon in 1972, Garey, Graham and Ullman [5], provided more detailed analysis of four heuristics: FirstFit , BestFit , FirstFitDecreasing (FFD) and BestFitDecreasing (BFD).”
BackgroundOn a dual version of the one-dimensional bin packing problem
Assmann, S. F., Johnson, D. S., Kleitman, D. J., & Leung, J. Y. ‐. (1984) · Journal of Algorithms · doi:10.1016/0196-6774(84)90004-x · Cited by 176
Introduction to NP-Completeness of Knapsack Problems
Kellerer, H., Pferschy, U., & Pisinger, D. (2004) · Knapsack Problems · doi:10.1007/978-3-540-24777-7_16 · Cited by 171 · cited 1×
“We refer the readers to [173] for detailed survey on 1-”
A algorithm for two-dimensional packing
Baker, B. S., Brown, D. J., & Katseff, H. P. (1981) · Journal of Algorithms · doi:10.1016/0196-6774(81)90034-1 · Cited by 154
On the performance of on-line algorithms for partition problems
Faigle, U., Kern, W., & Turán, G. (1989) · University of Twente Research Information · doi:10.5555/71777.71779 · Cited by 154
On the two-dimensional Knapsack Problem
Caprara, A., & Monaci, M. (2003) · Operations Research Letters · doi:10.1016/s0167-6377(03)00057-9 · Cited by 150 · cited 1×
“For 2-D geometric knapsack (GK), a result of Steinberg [76] for strip packing translates into a (3 + ε) approximation [144].”
BackgroundBin Packing Approximation Algorithms: Combinatorial Analysis
Coffman, E. G., Galambos, G., Martello, S., & Vigo, D. (1999) · Springer eBooks · doi:10.1007/978-1-4757-3023-4_3 · Cited by 145
There is no asymptotic PTAS for two-dimensional vector packing
Woeginger, G. J. (1997) · Information Processing Letters · doi:10.1016/s0020-0190(97)00179-8 · Cited by 145 · cited 1×
“Woeginger [159] showed that there exists no APTAS even for d = 2 unless P = NP.”
BackgroundAlgorithm Design for Computer System Design
Ausiello, G., Lucertini, M., & Serafini, P. (1984) · Courses and lectures · doi:10.1007/978-3-7091-4338-4 · Cited by 138
Probabilistic Analysis of Packing and Partitioning Algorithms
Coffman, E. G., & Lueker, G. S. (1991) · Medical Entomology and Zoology · Cited by 137
Approximation Algorithms for Bin Packing Problems: A Survey
Garey, M. R., & Johnson, D. S. (1981) · Springer eBooks · doi:10.1007/978-3-7091-2748-3_8 · Cited by 132
New lower bounds for certain classes of bin packing algorithms
Balogh, J., Békési, J., & Galambos, G. (2012) · Theoretical Computer Science · doi:10.1016/j.tcs.2012.04.017 · Cited by 130 · cited 1×
“54037 [60], improved from previous best 1.”
On-line bin packing in linear time
Ramanan, P., Brown, D. J., Lee, C. C., & Lee, D. T. (1989) · Journal of Algorithms · doi:10.1016/0196-6774(89)90031-x · Cited by 127 · cited 2×
“61217) [57],Harmonic++ (competitive ratio <1.”
BackgroundCoordination Complexity of Parallel Price-Directive Decomposition
Grigoriadis, M. D., & Khachiyan, L. G. (1996) · Mathematics of Operations Research · doi:10.1287/moor.21.2.321 · Cited by 123 · cited 1×
“Finally, Jansen and Solis-Oba gave an AFPTAS [70] by using the potential price directive decomposition method of Grigoriadis and Khachiyan [205].”
MethodFirst Fit bin packing: A tight analysis
Dósa, G., & Sgall, J. (2013) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.stacs.2013.538 · Cited by 121 · cited 1×
“7 Opt ⌋ [41] Greedy, online FirstFitDecreasing [7] 119 Opt + 69 [42] Presorting ⌊ 1 .”
A 2.5 times optimal algorithm for packing in two dimensions
Sleator, D. D. (1980) · Information Processing Letters · doi:10.1016/0020-0190(80)90121-0 · Cited by 117
Pagh, R. (2014) · Springer eBooks · doi:10.1007/978-3-642-27848-8 · Cited by 101
Tight absolute bound for First Fit Decreasing bin-packing: FFD(L)⩽11/9 OPT(L)+6/9
Dósa, G., Li, R., Han, X., & Tuza, Ź. (2013) · Theoretical Computer Science · doi:10.1016/j.tcs.2013.09.007 · Cited by 100
Multidimensional on-line bin packing: Algorithms and worst-case analysis
Coppersmith, D., & Raghavan, P. (1989) · Operations Research Letters · doi:10.1016/0167-6377(89)90027-8 · Cited by 96 · cited 3×
“Coppersmith and Raghavan [100] first studied online multidimensional GBP and gave algorithms with asymptotic competitive ratioof3.”
BackgroundBansal, N., Caprara, A., & Sviridenko, M. I. (2009) · SIAM Journal on Computing · doi:10.1137/080736831 · Cited by 96 · cited 9×
“The main idea behind this result is to show that the Round and Approx (R&A) framework introduced by Bansal, Caprara and Sviridenko [86] (See Section 2.4.5) can be applied to the ( 1 .”
BackgroundMethodInfluentialA Logarithmic Additive Integrality Gap for Bin Packing
Hoberg, R., & Rothvoß, T. (2017) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974782.172 · Cited by 95
Probabilistic analysis of packing and partitioning algorithms
Terno, J. (1992) · European Journal of Operational Research · doi:10.1016/0377-2217(92)90253-6 · Cited by 89
A better lower bound for on-line scheduling
Bartal, Y., Karloff, H. J., & Rabani, Y. (1994) · Information Processing Letters · doi:10.1016/0020-0190(94)00026-3 · Cited by 88
An on-line algorithm for multidimensional bin packing
Csirik, J., & van Vliet, A. (1993) · Operations Research Letters · doi:10.1016/0167-6377(93)90004-z · Cited by 88
Completeness in approximation classes
Crescenzi, P., & Panconesi, A. (1991) · Information and Computation · doi:10.1016/0890-5401(91)90025-w · Cited by 87
Packing 2-dimensional bins in harmony
Caprara, A. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2002.1181973 · Cited by 87 · cited 9×
“Caprara [82] showed the ratio of 2SBP versus 2-D GBP is also equal to T∞.”
BackgroundMethodResultInfluentialA branch-and-bound algorithm for the two-dimensional vector packing problem
Spieksma, F. C. R. (1994) · Computers & Operations Research · doi:10.1016/0305-0548(94)90059-0 · Cited by 82
On-line bin packing ? A restricted survey
Galambos, G., & Woeginger, G. J. (1995) · Mathematical Methods of Operations Research · doi:10.1007/bf01415672 · Cited by 80 · cited 7×
“Woeginger [159] showed that there exists no APTAS even for d = 2 unless P = NP .”
BackgroundInfluentialThe relative worst order ratio for online algorithms
Boyar, J., & Favrholdt, L. M. (2007) · ACM Transactions on Algorithms · doi:10.1145/1240233.1240245 · Cited by 78
Exact algorithms and APX-hardness results for geometric packing and covering problems
Chan, T. M., & Grant, E. (2012) · Computational Geometry · doi:10.1016/j.comgeo.2012.04.001 · Cited by 73 · cited 1×
“There aremany other related geometric packing/covering problems such asmaximum independent set rectangles [152], online square-into-square packing [154], geometric set cover/hitting set problem [155], anchored rectangle problem [156], maximal axis-parallel rectangles [157], circle/sphere packing [158] etc.”
BackgroundLi, K., & Cheng, K.-H. (1990) · SIAM Journal on Computing · doi:10.1137/0219059 · Cited by 71
There is no EPTAS for two-dimensional knapsack
Kulik, A., & Shachnai, H. (2010) · Information Processing Letters · doi:10.1016/j.ipl.2010.05.031 · Cited by 67 · cited 9×
“Ω ( d 1 − ε ) [167] Vector scheduling Offline ( d = 1) EPTAS [180] No FPTAS [177] Online ( d = 1) 1.9201 [195] 1.880 [196] Offline (constant d ) PTAS [160] No EPTAS [186] Offline (arbitrary d ) O ( log d loglog d ) [187,199] ω( 1 ) [160] Online O ( log d loglog d ) [199] Ω ( log d loglog d ) [199] Vector knapsack Offl…”
BackgroundInfluentialThe Accommodating Function: A Generalization of the Competitive Ratio
Boyar, J., Larsen, K. S., & Nielsen, M. N. (2001) · SIAM Journal on Computing · doi:10.1137/s0097539799361786 · Cited by 66 · cited 1×
“There are few others metrics to measure the quality of a packing, such as random-order ratio [33], accommodation function [34], relative worst-order ratio [35], differential approximation measure [36] etc.”
BackgroundMathematical Foundations of Computer Science 2002
Diks, K., & Rytter, W. (2002) · Lecture notes in computer science · doi:10.1007/3-540-45687-2 · Cited by 66
Shelf algorithms for on-line strip packing
Csirik, J., & Woeginger, G. J. (1997) · Information Processing Letters · doi:10.1016/s0020-0190(97)00120-8 · Cited by 64
Approximating Bin Packing within O(log OPT · Log Log OPT) Bins
Rothvoß, T. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.11 · Cited by 63
Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
Golan, I. (1981) · SIAM Journal on Computing · doi:10.1137/0210042 · Cited by 61 · cited 1×
“After a sequence of improvements [126,127], the seminal work of Kenyon and Rémila [90] provided an APTAS with”
MethodLower bounds for on-line two-dimensional packing algorithms
Brown, D., Baker, B. S., & Katseff, H. P. (1982) · Acta Informatica · doi:10.1007/bf00264439 · Cited by 60
A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing
Baker, B. S., & Coffman, Jr. (1981) · SIAM Journal on Algebraic Discrete Methods · doi:10.1137/0602019 · Cited by 59 · cited 1×
“NextFitDecreasing [7] T∞ · Opt + O(1) [40] Presorting”
Tight bounds for online vector bin packing
Azar, Y., Cohen, I. R., Kamara, S., & Shepherd, F. B. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488730 · Cited by 59 · cited 1×
“[167] settled the status by giving Ω(d1−ε) information theoretic lower bound using stochastic packing integer programs and online graph coloring problem [168] where a sequence of nodes arrives online along with edges to previously arrived neighbors and the transparent adversary reveals the color it gives to a node imm…”
BackgroundOptimal Analysis of Best Fit Bin Packing
Dósa, G., & Sgall, J. (2014) · Lecture notes in computer science · doi:10.1007/978-3-662-43948-7_36 · Cited by 58 · cited 1×
“7Opt⌋ [43] Greedy, online de la Vega and Lueker [37] (1 + ε)Opt + O( 1 ε2 ) Linear grouping Karp and Karmarkar [28] Opt + O(log2 Opt) Iterative rounding”
BackgroundOptimal Online Algorithms for Multidimensional Packing Problems
Epstein, L., & van Stee, R. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539705446895 · Cited by 55 · cited 3×
“Epstein and van Stee [92] achieved the same ratio of T d ∞ only using bounded space and showed it to be the optimal among all bounded space algorithms.”
BackgroundInfluentialBetter approximation algorithms for bin covering
Csirik, J., Johnson, D. S., & Kenyon, C. (2001) · doi:10.5555/365411.365533 · Cited by 54
An asymptotic fully polynomial time approximation scheme for bin covering
Jansen, K., & Solis-Oba, R. (2003) · Theoretical Computer Science · doi:10.1016/s0304-3975(03)00363-3 · Cited by 51 · cited 3×
“Finally, Jansen and Solis-Oba gave an AFPTAS [70] by using the potential price directive decomposition method of Grigoriadis and Khachiyan [205].”
BackgroundMethodDifferential approximation algorithms for some combinatorial optimization problems
Demange, M., Grisoni, P., & Paschos, V. T. (1998) · Theoretical Computer Science · doi:10.1016/s0304-3975(97)00099-6 · Cited by 51 · cited 1×
“There are few others metrics to measure the quality of a packing, such as random-order ratio [33], accommodation function [34], relative worst-order ratio [35], differential approximation measure [36] etc.”
BackgroundImproved Approximation Algorithm for Two-Dimensional Bin Packing
Bansal, N. N., & Khan, A. (2014) · Cited by 49
Self-citationHeuristic algorithms for on-line packing in three dimensions
Li, K., & Cheng, K. H. (1992) · Journal of Algorithms · doi:10.1016/0196-6774(92)90058-k · Cited by 46 · cited 1×
“89 [138] using theHarmonic algorithm as a subroutine.”
MethodOnline square and cube packing
Epstein, L., & van Stee, R. (2005) · Acta Informatica · doi:10.1007/s00236-005-0169-z · Cited by 46 · cited 18×
“Later, Epstein and van Stee [110] gave a asymptotic approximation.”
BackgroundInfluentialA new upper bound 2.5545 on 2D Online Bin Packing
Han, X., Chin, F. Y. L., Ting, H., Zhang, G., & Zhang, Y. (2011) · ACM Transactions on Algorithms · doi:10.1145/2000807.2000818 · Cited by 45 · cited 1×
“[103] gave an improved upper bound of 2.”
BackgroundAnalysis and Design of Algorithms in Combinatorial Optimization
Ausiello, G., & Lucertini, M. (1981) · Springer eBooks · doi:10.1007/978-3-7091-2748-3 · Cited by 43 · cited 6×
“In fact the term approximation algorithm was coined by David S. Johnson [10] in an influential and prescient paper in 1973 where he studied algorithms for bin packing and other packing and covering related optimization problems.”
BackgroundInfluentialThe pallet loading problem: A survey
Ram, B. (1992) · International Journal of Production Economics · doi:10.1016/0925-5273(92)90034-5 · Cited by 40 · cited 1×
“This variant and other higher dimensional GBP variants have vast applications in cutting stock, vehicle loading, pallet packing, memory allocation and several other logistics and robotics related problems [1,21].”
BackgroundNew bounds for multi-dimensional packing
Seiden, S. S., & van Stee, R. (2002) · Symposium on Discrete Algorithms · doi:10.5555/545381.545447 · Cited by 40
Problems in discrete applied mathematics
Assmann, S. F. (1983) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 39
Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
Caprara, A., Lodi, A., & Monaci, M. (2005) · Mathematics of Operations Research · doi:10.1287/moor.1040.0112 · Cited by 34 · cited 1×
“As there are PTAS for 2-stage packing [74], this will give another 3/2 approximation for 2-D BP and coupled with R&A method this will”
MethodA Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability
Bansal, N., Caprara, A., Jansen, K., Prädel, L., & Sviridenko, M. I. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-10631-6_10 · Cited by 31
Tight Bounds for Online Vector Scheduling
Im, S., Kell, N., Kulkarni, J., & Panigrahi, D. (2015) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2015.39 · Cited by 29 · cited 4×
“Online O( log d log log d ) [199] Ω( log d log log d ) [199]”
BackgroundMethodInfluentialPacking Problems with Orthogonal Rotations
Miyazawa, F. K., & Wakabayashi, Y. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24698-5_40 · Cited by 29 · cited 4×
“In terms of asymptotic approximation, Miyazawa and Wakabayashi [91] gave an algorithm with asymptotic performance ratio of 1.613.”
MethodInfluentialA note on online hypercube packing
Han, X., Ye, D., & Zhou, Y. G. (2009) · Central European Journal of Operations Research · doi:10.1007/s10100-009-0109-z · Cited by 26
Two-dimensional on-line bin packing problem with rotatable items
Fujita, S., & Hada, T. (2002) · Theoretical Computer Science · doi:10.1016/s0304-3975(01)00410-8 · Cited by 25 · cited 2×
“Fujita and Hada [107] first considered 2-”
BackgroundBounds for online bounded space hypercube packing
Epstein, L., & van Stee, R. (2006) · Discrete Optimization · doi:10.1016/j.disopt.2006.11.005 · Cited by 24 · cited 17×
“Later, Epstein and van Stee [110] gave a asymptotic approximation.”
InfluentialHarmonic algorithm for 3-dimensional strip packing problem
Bansal, N., Han, X., Iwama, K., Sviridenko, M. I., & Zhang, G. (2007) · doi:10.5555/1283383.1283512 · Cited by 23
Two-dimensional online bin packing with rotation
Epstein, L. (2010) · Theoretical Computer Science · doi:10.1016/j.tcs.2010.04.021 · Cited by 23 · cited 1×
“Epstein [108] gave an improved bounded space algorithm with competitive ratio 2.”
BackgroundThe optimal absolute ratio for online bin packing
Balogh, J., Békési, J., Dósa, G., Sgall, J., & van Stee, R. (2015) · Figshare · Cited by 21
Karger, D. R., & Onak, K. (2007) · Symposium on Discrete Algorithms · doi:10.5555/1283383.1283513 · Cited by 20
A Lower Bound for On-Line Vector-Packing Algorithms.
Galambos, G., Kellerer, H. G., & Woeginger, G. J. (1993) · Acta Cybernetica · Cited by 19
Online Lower Bounds via Duality
Azar, Y., Cohen, I. R., & Roytman, A. (2017) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1137/1.9781611974782.66 · Cited by 18
The optimal absolute ratio for online bin packing
Balogh, J., Békési, J., Dósa, G., Sgall, J., & Stee, R. V. (2015) · Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms · doi:10.1137/1.9781611973730.94 · Cited by 17
Two Dimensional Packing: The Power of Rotation
Epstein, L. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45138-9_34 · Cited by 16
Power strip packing of malleable demands in smart grid
Karbasioun, M. M., Shaikhet, G., Kranakis, E., & Lambadaris, I. (2013) · International Conference on Communications · doi:10.1109/icc.2013.6655233 · Cited by 16
Approximation algorithms for multidimensional bin packing
Khan, A. (2015) · SMARTech Repository (Georgia Institute of Technology) · Cited by 14
Self-citationMultidimensional Cube Packing☆
Kohayakawa, Y., Miyazawa, F. K., Raghavan, P., & Wakabayashi, Y. (2001) · Electronic Notes in Discrete Mathematics · doi:10.1016/s1571-0653(04)00237-9 · Cited by 10
Approximate strip packing: Revisited
Han, X., Iwama, K., Ye, D., & Zhang, G. (2016) · Information and Computation · doi:10.1016/j.ic.2016.03.010 · Cited by 8
SIGACT news online algorithms column 20: the power of harmony
van Stee, R. (2012) · ACM SIGACT News · doi:10.1145/2261417.2261440 · Cited by 7 · cited 2×
“We refer the readers to [63] for more variants (such as dynamic bin packing, bin packing with rejections, bin packing with cardinality constraints, resource augmentation etc.”
BackgroundImproved Lower Bounds for Online Hypercube Packing
Heydrich, S., & van Stee, R. (2016) · MPG.PuRe (Max Planck Society) · Cited by 5
Two-Dimensional Bin Packing Problem with Guillotine Restrictions
Elettrica, E., & Marconi, G. (2015) · Cited by 2
Harmonic Algorithm for Bin Packing
Epstein, L. (2014) · Springer eBooks · doi:10.1007/978-3-642-27848-8_490-1 · Cited by 1 · cited 1×
“We refer the readers to [85] for more related applications of theHarmonic algorithm in online and bounded space algorithms.”
Method
Cited by
Online Bin Packing with Predictions
Angelopoulos, S., Kamali, S., & Shadkami, K. (2022) · Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2022/635 · Cited by 28
Metadata
- Authors
- Christensen, H. I., Khan, A., Pokutta, S., & Tetali, P.
- Venue
- Computer Science Review
- Publisher
- Elsevier BV
- Published
- 2017-05
- Volume
- 24
- Pages
- 63-79
- ISSN
- 1574-0137 (ISSN-L)
- OpenAlex
- W2577702044
- Cited by
- 237
- References
- 116
- FWCI
- 20.99
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.