High-multiplicity bin packing
ಹೆಚ್ಚಿನ-ಮಲ್ಟಿಪ್ಲಿಸಿಟಿ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಎಂಬುದು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ ಸಮಸ್ಯೆಯ ಒಂದು ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದೆ, ಇದರಲ್ಲಿ ವಿವಿಧ ಗಾತ್ರದ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯು ಚಿಕ್ಕದಾಗಿದೆ, ಆದರೆ ಪ್ರತಿ ಗಾತ್ರದ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯು ದೊಡ್ಡದಾಗಿದೆ. ಸಾಮಾನ್ಯ ಬಿನ್-ಪ್ಯಾಕಿಂಗ್ ಸಮಸ್ಯೆಯು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಆಗಿದ್ದರೂ, ವಿವಿಧ ಗಾತ್ರಗಳ ಸಂಖ್ಯೆಯು ಸ್ಥಿರ ಸ್ಥಿರಾಂಕವಾಗಿದೆ ಎಂದು ಭಾವಿಸಿ, ಹೆಚ್ಚಿನ-ಮಲ್ಟಿಪ್ಲಿಸಿಟಿ ಸೆಟ್ಟಿಂಗ್ ಅನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. ಸಮಸ್ಯೆಯ ವ್ಯಾಖ್ಯಾನ ಸಮಸ್ಯೆಯ ಒಳಹರಿವುಗಳು ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕಗಳಾಗಿವೆಃ ಡಿ-ವಿವಿಧ ಗಾತ್ರಗಳ ಸಂಖ್ಯೆ (ಸಮಸ್ಯೆಯ ಆಯಾಮ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ); ಬಿ-ಬಿನ್ ಸಾಮರ್ಥ್ಯ. s1,., sd-ಗಾತ್ರಗಳು. ಗಾತ್ರಗಳ ವಾಹಕವನ್ನು s. n1,., nd-ಗುಣಾಕಾರಗಳಿಂದ ಸೂಚಿಸಲಾಗುತ್ತದೆ; ni ಎಂದರೆ ಗಾತ್ರವನ್ನು ಹೊಂದಿರುವ ವಸ್ತುಗಳ ಸಂಖ್ಯೆ. ಗುಣಾಕಾರಗಳ ವಾಹಕವನ್ನು n ನಿಂದ ಸೂಚಿಸಲಾಗುತ್ತದೆ. n ಒಟ್ಟು ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ, ಅಂದರೆ, n = n1 +. + nd. ಸಮಸ್ಯೆಯ ವಿವರಣೆಯಲ್ಲಿ ಕಂಡುಬರುವ ಅತಿದೊಡ್ಡ ಪೂರ್ಣಾಂಕವನ್ನು V ಸೂಚಿಸುತ್ತದೆ, ಅಂದರೆ, V = ಗರಿಷ್ಠ (s1,., sd, n1,., nd, B) ಔಟ್ಪುಟ್ ಒಂದು ಪ್ಯಾಕಿಂಗ್ ಆಗಿದೆ-ಪ್ರತಿ ಬಿನ್ನಲ್ಲಿನ ವಸ್ತುಗಳ ಒಟ್ಟು ಗಾತ್ರವು ಗರಿಷ್ಠ B ಆಗಿರುತ್ತದೆ ಮತ್ತು ಇದಕ್ಕೆ ಒಳಪಟ್ಟು, ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯು ಸಾಧ್ಯವಾದಷ್ಟು ಚಿಕ್ಕದಾಗಿದೆ. ಉದಾಹರಣೆಃ ಡಿ = 2, ಎಸ್ 1 = 30, ಎಸ್ 2 = 40, ಎನ್ 1 = ಎನ್ 2 = 5, ಬಿ = 120 ಎಂದು ಭಾವಿಸೋಣ. ಆದ್ದರಿಂದ ಗಾತ್ರಗಳೊಂದಿಗೆ n = 10 ವಸ್ತುಗಳು ಇವೆಃ 30,30,30,30,30,40,40,40,40,40. ನಂತರ, ಸಂಭಾವ್ಯ ಪ್ಯಾಕಿಂಗ್ ಎಂದರೆಃ {30,30,30,30}, {40,40,40}, {30,40,40}, ಇದು 3 ತೊಟ್ಟಿಗಳನ್ನು ಬಳಸುತ್ತದೆ. ಸಂರಚನೆಗಳು ಒಂದು ಸಂರಚನೆಯು ಒಂದೇ ಬಿನ್ನಲ್ಲಿ ಹೊಂದಿಕೊಳ್ಳಬಹುದಾದ ವಸ್ತುಗಳ ಗುಂಪಾಗಿದೆ. ಇದನ್ನು ಡಿ ಪೂರ್ಣಾಂಕಗಳ ವಾಹಕದಿಂದ ಪ್ರತಿನಿಧಿಸಬಹುದು, ಇದು ಸಂರಚನೆಯಲ್ಲಿ ವಿವಿಧ ಗಾತ್ರಗಳ ಗುಣಾಕಾರಗಳನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಔಪಚಾರಿಕವಾಗಿ, ಪ್ರತಿ ಸಂರಚನೆ c ಗೆ ನಾವು ಪೂರ್ಣಾಂಕ ವೆಕ್ಟರ್ ac = ac, 1,., ac, d ಅನ್ನು ವ್ಯಾಖ್ಯಾನಿಸುತ್ತೇವೆ, ಅಂದರೆ ac ≤ n ಮತ್ತು ac·s ≤ B. ಮೇಲಿನ ಉದಾಹರಣೆಯಲ್ಲಿ, 1 * 30+2 * 40 ≤120 ರಿಂದ, ಒಂದು ಸಂರಚನೆಯು c = {30,40,40} ಆಗಿದೆ. ಇದರ ಅನುಗುಣವಾದ ವಾಹಕವು ಎಸಿ = (1,2) ಆಗಿದೆ. ಇತರ ಸಂರಚನಾ ವಾಹಕಗಳೆಂದರೆ (4,0), (3,0), (2,0), (2,1), (1,0), (1,1), (1,2), (0,1), (0,2), (0,3). ನಾವು 3 ಗಾತ್ರದ ಕೇವಲ ಮೂರು ವಸ್ತುಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ನಾವು (4,0) ಸಂರಚನೆಯನ್ನು ಬಳಸಲು ಸಾಧ್ಯವಾಗಲಿಲ್ಲ. ಸಂರಚನೆಯ ರೇಖೀಯ ಕ್ರಮಾವಳಿಯನ್ನು ಬಳಸಿಕೊಂಡು ಸಮಸ್ಯೆಯನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಲು ಸಾಧ್ಯವಿದೆಃ ಪ್ರತಿ ಸಂರಚನೆ c ಗೆ, ಚಲಪರಿಮಾಣ xc ಇರುತ್ತದೆ, ಇದು c ಅನ್ನು ಬಳಸುವ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಬಳಸಿದ ತೊಟ್ಟಿಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆಯು ಎಲ್ಲಾ ಸಂರಚನೆಗಳ ಮೇಲೆ xc ಯ ಮೊತ್ತವಾಗಿದೆ, ಇದನ್ನು 1·x ನಿಂದ ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಪ್ರತಿ ಗಾತ್ರದಿಂದ ಬಳಸಲಾಗುವ ವಸ್ತುಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆಯು ಎಲ್ಲಾ ಸಂರಚನೆಗಳ ಮೇಲೆ ವಾಹಕಗಳ ಮೊತ್ತವಾಗಿದೆ c. ನಂತರ, ಸಮಸ್ಯೆ ಎಂದರೆ 1·x ಅನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು, ಅಂದರೆ ಎಲ್ಲಾ ಸಂರಚನೆಗಳ ಮೇಲೆ ಎಸಿ·ಎಕ್ಸ್ಸಿ ಮೊತ್ತವು ಕನಿಷ್ಠ n ಆಗಿರುತ್ತದೆ, ಇದರಿಂದಾಗಿ ಎಲ್ಲಾ ವಸ್ತುಗಳು ಪ್ಯಾಕ್ ಆಗುತ್ತವೆ. ಅಲ್ಗಾರಿದಮ್ಗಳು ಮೂಲ ಅಲ್ಗಾರಿದಮ್ಗಳು ಮೊದಲು ಎಲ್ಲಾ ವಸ್ತುಗಳು ದೊಡ್ಡದಾಗಿವೆ ಎಂದು ಭಾವಿಸೋಣ, ಅಂದರೆ, ಪ್ರತಿಎಸ್ಐ ಕೆಲವು ಭಿನ್ನರಾಶಿಗಳಿಗೆ ಕನಿಷ್ಠ e·B ಆಗಿರುತ್ತದೆ. ನಂತರ, ಪ್ರತಿ ಬಿನ್ನಲ್ಲಿರುವ ಒಟ್ಟು ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ 1/e ಆಗಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ಒಟ್ಟು ಸಂರಚನೆಯ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ d1/e ಆಗಿರುತ್ತದೆ. ಪ್ರತಿ ಸಂರಚನೆಯು ಗರಿಷ್ಠ n ಬಾರಿ ಕಾಣಿಸಿಕೊಳ್ಳುತ್ತದೆ. ಆದ್ದರಿಂದ, ಪರಿಶೀಲಿಸಲು ಹೆಚ್ಚಿನ ಸಂಯೋಜನೆಗಳಿವೆ. ಪ್ರತಿ ಸಂಯೋಜನೆಗೆ, ನಾವು ಡಿ ನಿರ್ಬಂಧಗಳನ್ನು (ಪ್ರತಿ ಗಾತ್ರಕ್ಕೆ ಒಂದು) ಪರಿಶೀಲಿಸಬೇಕು, ಆದ್ದರಿಂದ ರನ್-ಟೈಮ್, ಇದು ಡಿ, ಇ ಸ್ಥಿರವಾಗಿದ್ದಾಗ ಎನ್ ನಲ್ಲಿ ಬಹುಪದವಾಗಿದೆ. ಈ ಅಲ್ಗಾರಿದಮ್ನ ಮುಖ್ಯ ಸಮಸ್ಯೆಯೆಂದರೆ (ವಸ್ತುಗಳು ದೊಡ್ಡದಾಗಿದ್ದಾಗ ಮಾತ್ರ ಇದು ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ ಎಂಬ ಅಂಶವನ್ನು ಹೊರತುಪಡಿಸಿ) ಅದರ ರನ್ಟೈಮ್ n ನಲ್ಲಿ ಬಹುಪದವಾಗಿದೆ, ಆದರೆ ಇನ್ಪುಟ್ನ ಉದ್ದವು (ಬೈನರಿ ಪ್ರಾತಿನಿಧ್ಯದಲ್ಲಿ) ಲಾಗ್ (ವಿ) ನಲ್ಲಿ ರೇಖೀಯವಾಗಿರುತ್ತದೆ, ಇದು ಲಾಗ್ (ಎನ್) ನ ಪ್ರಮಾಣದ ಕ್ರಮದಲ್ಲಿದೆ. ಇನ್ಪುಟ್ ಗಾತ್ರದ ಫಿಲಿಪಿ ಮತ್ತು ಅಗ್ನೆಟಿಸ್ನಲ್ಲಿ ರನ್-ಟೈಮ್ ಬಹುಪದವು ಒ (ಪಾಲಿ (ಲಾಗ್ ವಿ)) ಸಮಯದಲ್ಲಿ ಗರಿಷ್ಠ ಒಪಿಟಿ + ಡಿ-2 ತೊಟ್ಟಿಗಳೊಂದಿಗೆ ಪರಿಹಾರವನ್ನು ಕಂಡುಕೊಳ್ಳುವ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಿತು. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, d = 2 ವಿಭಿನ್ನ ಗಾತ್ರಗಳಿಗೆ, ಅವುಗಳ ಕ್ರಮಾವಳಿಯು O (ಲಾಗ್ V) ಸಮಯದಲ್ಲಿ ಸೂಕ್ತವಾದ ಪರಿಹಾರವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ಗೋಯೆಮನ್ಸ್ ಮತ್ತು ರಾಥ್ವೋಸ್ ಯಾವುದೇ ಸ್ಥಿರ ಡಿಗೆ ಒಂದು ಕ್ರಮಾವಳಿಯನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಿದರು, ಇದು ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳನ್ನು ಬೈನರಿ ಎನ್ಕೋಡಿಂಗ್ನಲ್ಲಿ ನೀಡಿದಾಗ ಸೂಕ್ತವಾದ ಪರಿಹಾರವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ಅವರ ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುತ್ತದೆಃ ಪಿ ಮತ್ತು ಕ್ಯೂ ಎಂಬ ಎರಡು ಡಿ-ಆಯಾಮದ ಪಾಲಿಟೋಪ್ಗಳನ್ನು ನೀಡಿದರೆ, ಪಿ ಯಲ್ಲಿ ಕನಿಷ್ಠ ಸಂಖ್ಯೆಯ ಪೂರ್ಣಾಂಕ ಬಿಂದುಗಳನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ, ಅದರ ಮೊತ್ತವು ಕ್ಯೂ ನಲ್ಲಿದೆ. ಅವರ ಅಲ್ಗಾರಿದಮ್ ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಅವರ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಇತರ ಸಮಸ್ಯೆಗಳಿಗೆ ಅಳವಡಿಸಿಕೊಳ್ಳಬಹುದು, ಉದಾಹರಣೆಗೆ ಒಂದೇ-ಯಂತ್ರಗಳ ವೇಳಾಪಟ್ಟಿ ಮತ್ತು ವಿವಿಧ ನಿರ್ಬಂಧಗಳೊಂದಿಗೆ ಸಂಬಂಧವಿಲ್ಲದ-ಯಂತ್ರಗಳ ವೇಳಾಪಟ್ಟಿ. ಸಾಮಾನ್ಯ ಬಿನ್-ಪ್ಯಾಕಿಂಗ್ ಸಮಸ್ಯೆಗಾಗಿ ಹಲವಾರು ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳು ಈ ಕೆಳಗಿನ ಯೋಜನೆಯನ್ನು ಬಳಸುತ್ತವೆಃ ವಸ್ತುಗಳನ್ನು "ಸಣ್ಣ" (ಇಬಿಗಿಂತ ಚಿಕ್ಕದು, ಕೆಲವು ಭಾಗಗಳಿಗೆ ಇ (0,1)) ಮತ್ತು "ದೊಡ್ಡ" (ಕನಿಷ್ಠ ಇಬಿ) ಎಂದು ಬೇರ್ಪಡಿಸಿ. ದೊಡ್ಡ ವಸ್ತುಗಳನ್ನು ಮೊದಲು ನಿರ್ವಹಿಸಿಃ ವಿವಿಧ ಗಾತ್ರಗಳ ಸಂಖ್ಯೆಯು ಹೆಚ್ಚುಕಡಿಮೆ ಸ್ಥಿರವಾಗಿರಬಹುದಾದ ರೀತಿಯಲ್ಲಿ ವಸ್ತುವಿನ ಗಾತ್ರಗಳನ್ನು ಸುತ್ತಿಕೊಳ್ಳಿ. ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ದುರಾಸೆಯಿಂದ ಹಂಚಿಕೊಳ್ಳಿ, ಉದಾಹರಣೆಗೆ. ನೆಕ್ಸ್ಟ್-ಫಿಟ್ ಬಿನ್ ಪ್ಯಾಕಿಂಗ್ನೊಂದಿಗೆ. ಯಾವುದೇ ಹೊಸ ತೊಟ್ಟಿಗಳನ್ನು ರಚಿಸದಿದ್ದರೆ, ನಾವು ಮುಗಿಸಿದ್ದೇವೆ. ಹೊಸ ತೊಟ್ಟಿಗಳನ್ನು ರಚಿಸಿದರೆ, ಇದರರ್ಥ ಎಲ್ಲಾ ತೊಟ್ಟಿಗಳು (ಬಹುಶಃ ಕೊನೆಯದನ್ನು ಹೊರತುಪಡಿಸಿ) ಕನಿಷ್ಠ (1-ಇ) ಬಿ ವರೆಗೆ ತುಂಬಿರುತ್ತವೆ. ಆದ್ದರಿಂದ, ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ ಒಪಿಟಿ/(1-ಇ) + 1 ≤ (1 + 2ಇ) ಒಪಿಟಿ + 1 ಆಗಿರುತ್ತದೆ. ಕ್ರಮಾವಳಿಗಳು ನಿದರ್ಶನವನ್ನು ಹೇಗೆ ಸುತ್ತುತ್ತವೆ ಎಂಬುದರಲ್ಲಿ ಭಿನ್ನವಾಗಿರುತ್ತವೆ. ಲೀನಿಯರ್ ರೌಂಡಿಂಗ್ ಲ್ಯೂಕರ್ ಮತ್ತು ಡಿ-ಲಾ-ವೇಗಾ ಮತ್ತು ಅಡಾಪ್ಟಿವ್ ಇನ್ಪುಟ್ ರೌಂಡಿಂಗ್ ಕಲ್ಪನೆಯನ್ನು ಕಂಡುಹಿಡಿದರು. ವಸ್ತುಗಳನ್ನು ಅವುಗಳ ಗಾತ್ರದ ಪ್ರಕಾರ ಆರ್ಡರ್ ಮಾಡಿ, ಮತ್ತು ಅವುಗಳನ್ನು 1/ಇ2 ಕಾರ್ಡಿನಲಿಟಿ ಎನ್ಇ2 ಗುಂಪುಗಳಾಗಿ ವರ್ಗೀಕರಿಸಿ. ಪ್ರತಿ ಗುಂಪಿನಲ್ಲಿ, ಗಾತ್ರಗಳನ್ನು ಗುಂಪಿನಲ್ಲಿ ಗರಿಷ್ಠ ಗಾತ್ರಕ್ಕೆ ಸುತ್ತಿಕೊಳ್ಳಿ. ಈಗ, ಕೇವಲ d = 1/e2 ವಿವಿಧ ಗಾತ್ರಗಳಿವೆ. ದುಂಡಾದ ನಿದರ್ಶನದ ಪರಿಹಾರವು ಮೂಲ ನಿದರ್ಶನಕ್ಕೂ ಸಹ ಕಾರ್ಯಸಾಧ್ಯವಾಗಿದೆ, ಆದರೆ ತೊಟ್ಟಿಗಳ ಸಂಖ್ಯೆಯು ಅಗತ್ಯಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿರಬಹುದು. ನಷ್ಟವನ್ನು ಪ್ರಮಾಣೀಕರಿಸಲು, ಹಿಂದಿನ ಗುಂಪಿನಲ್ಲಿನ ಗರಿಷ್ಠ ಗಾತ್ರಕ್ಕೆ ಪೂರ್ಣಾಂಕವನ್ನು ಪರಿಗಣಿಸಿ (ಮೊದಲ ಗುಂಪನ್ನು 0ಕ್ಕೆ ಪೂರ್ಣಾಂಕಗೊಳಿಸಲಾಗಿದೆ). ದುಂಡಾದ-ಕೆಳಗೆ ಉದಾಹರಣೆ D ಯು ದುಂಡಾದ-ಅಪ್ ಉದಾಹರಣೆ U ಗೆ ಬಹುತೇಕ ಸಮನಾಗಿರುತ್ತದೆ, D ಯಲ್ಲಿ ಕೆಲವು ne2 ಸೊನ್ನೆಗಳಿವೆ ಆದರೆ U ನಲ್ಲಿ ಕೆಲವು ne2 ದೊಡ್ಡ ವಸ್ತುಗಳು ಇವೆ; ಆದರೆ ಅವುಗಳ ಗಾತ್ರವು ಗರಿಷ್ಠ B ಆಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ಯು ಗೆ ಡಿ ಗಿಂತ ಹೆಚ್ಚಿನ ಎನ್ಇ2 ಹೆಚ್ಚು ತೊಟ್ಟಿಗಳು ಬೇಕಾಗುತ್ತವೆ. ಡಿ ಗೆ ಗರಿಷ್ಠಕ್ಕಿಂತ ಕಡಿಮೆ ತೊಟ್ಟಿಗಳು ಬೇಕಾಗುವುದರಿಂದ, ನಾವು ಆ ಬಿನ್ (ಯು) ≤ ಒಪಿಟಿ + ಎನ್ಇ2 ಅನ್ನು ಪಡೆಯುತ್ತೇವೆ, ಅಂದರೆ, ನಾವು ಇ ಅನ್ನು ಆಯ್ಕೆ ಮಾಡುವ ಮೂಲಕ ನಾವು ಇಷ್ಟಪಡುವಷ್ಟು ಚಿಕ್ಕದಾಗಿರುವ ಒಂದು ಸಂಯೋಜಕ ದೋಷವನ್ನು ಹೊಂದಿದ್ದೇವೆ. ಎಲ್ಲಾ ವಸ್ತುಗಳು ದೊಡ್ಡದಾಗಿದ್ದರೆ (ಕನಿಷ್ಠ ಇಬಿ ಗಾತ್ರದ), ಒಪಿಟಿಯಲ್ಲಿನ ಪ್ರತಿ ಬಿನ್ ಗರಿಷ್ಠ 1/ಇ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ (ಕನಿಷ್ಠ ಇಬಿ ಗಾತ್ರದ), ಆದ್ದರಿಂದ ಒಪಿಟಿ ಕನಿಷ್ಠ ಎನ್ ಆಗಿರಬೇಕು. ಆದ್ದರಿಂದ, ಬಿನ್ (ಯು) ≤ (1 + ಇ) ಒಪಿಟಿ. ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ನಿರ್ವಹಿಸಿದ ನಂತರ, ನಾವು ಹೆಚ್ಚಿನದನ್ನು ಪಡೆಯುತ್ತೇವೆ. ಜ್ಯಾಮಿತೀಯ ಪೂರ್ಣಾಂಕ ಕರ್ಮರ್ಕರ್ ಮತ್ತು ಕಾರ್ಪ್ ಅವರು ಹೆಚ್ಚು ಪರಿಣಾಮಕಾರಿ ಪೂರ್ಣಾಂಕ ವಿಧಾನವನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ, ಇದನ್ನು ಅವರು ಜ್ಯಾಮಿತೀಯ ಪೂರ್ಣಾಂಕ ಎಂದು ಕರೆಯುತ್ತಾರೆ (ಡಿ-ಲಾ-ವೇಗಾ ಮತ್ತು ಲ್ಯೂಕರ್ನ ರೇಖೀಯ ಪೂರ್ಣಾಂಕಕ್ಕೆ ವ್ಯತಿರಿಕ್ತವಾಗಿ). ಈ ನಾವೀನ್ಯತೆಗಳ ಆಧಾರದ ಮೇಲೆ, ಅವರು ಮತ್ತು ನಲ್ಲಿ ರನ್-ಟೈಮ್ ಬಹುಪದದೊಂದಿಗೆ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ಅವರ ಅಲ್ಗಾರಿದಮ್ ಗರಿಷ್ಠ ಗಾತ್ರದೊಂದಿಗೆ ಪರಿಹಾರವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ. ಸುಧಾರಣೆಗಳು ಈ ತಂತ್ರವನ್ನು ನಂತರ ಹಲವಾರು ಲೇಖಕರು ಸುಧಾರಿಸಿದರುಃ ರಾಥ್ವಾಸ್ ಗರಿಷ್ಠ ಗಾತ್ರದೊಂದಿಗೆ ಪರಿಹಾರವನ್ನು ಉತ್ಪಾದಿಸುವ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಿದರು. ಹೋಬರ್ಗ್ ಮತ್ತು ರಾಥ್ವೋಸ್ ಈ ಕ್ರಮಾವಳಿಯನ್ನು ಗಾತ್ರದೊಂದಿಗೆ ಪರಿಹಾರವನ್ನು ಉತ್ಪಾದಿಸಲು ಸುಧಾರಿಸಿದರು. ಅಲ್ಗಾರಿದಮ್ ಯಾದೃಚ್ಛಿಕವಾಗಿದೆ, ಮತ್ತು ಅದರ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವು ಒಟ್ಟು ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯಲ್ಲಿ ಬಹುಪದವಾಗಿದೆ. ಕಟಿಂಗ್ ಸ್ಟಾಕ್ ಸಮಸ್ಯೆಯನ್ನು ಸಹ ನೋಡಿ-ಹೆಚ್ಚಿನ-ಮಲ್ಟಿಪ್ಲಿಸಿಟಿ ಬಿನ್-ಪ್ಯಾಕಿಂಗ್ನಂತೆಯೇ, ಆದರೆ ಬಿನ್ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಹೊರತುಪಡಿಸಿ, ಪ್ರತಿ ಬಿನ್ನಲ್ಲಿ ಒಟ್ಟು ವ್ಯರ್ಥವಾದ ಜಾಗವನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಗುರಿಯಾಗಿದೆ. ಇದಲ್ಲದೆ, ಕೆಲವು ರೂಪಾಂತರಗಳಲ್ಲಿ, ಪ್ರತಿ ಗಾತ್ರದ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯನ್ನು ನಿಗದಿಪಡಿಸಲಾಗಿಲ್ಲ, ಆದರೆ ಕೆಲವು ನಿರ್ದಿಷ್ಟ ಕೆಳ ಮತ್ತು ಮೇಲಿನ ಮಿತಿಗಳ ನಡುವೆ ಚಲಿಸಬಹುದು. ಉಲ್ಲೇಖಗಳು ಬಿನ್ ಪ್ಯಾಕಿಂಗ್