Longest-processing-time-first scheduling
ಲಾಂಗ್-ಪ್ರೊಸೆಸಿಂಗ್-ಟೈಮ್-ಫಸ್ಟ್ (ಎಲ್ಪಿಟಿ) ಎಂಬುದು ಉದ್ಯೋಗ ವೇಳಾಪಟ್ಟಿಗಾಗಿ ಒಂದು ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ಅಲ್ಗಾರಿದಮ್ಗೆ ಇನ್ಪುಟ್ ಎನ್ನುವುದು ಉದ್ಯೋಗಗಳ ಒಂದು ಗುಂಪಾಗಿದೆ, ಪ್ರತಿಯೊಂದೂ ನಿರ್ದಿಷ್ಟ ಸಂಸ್ಕರಣಾ ಸಮಯವನ್ನು ಹೊಂದಿದೆ. ಕೆಲಸಗಳನ್ನು ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಬಲ್ಲ ಯಂತ್ರಗಳ ಸಂಖ್ಯೆಯನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸುವ ಒಂದು ಸಂಖ್ಯೆ m ಸಹ ಇದೆ. ಎಲ್ಪಿಟಿ ಅಲ್ಗಾರಿದಮ್ ಈ ಕೆಳಗಿನಂತೆ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆಃ ಕೆಲಸಗಳನ್ನು ಅವುಗಳ ಸಂಸ್ಕರಣಾ-ಸಮಯದ ಅವರೋಹಣ ಕ್ರಮದ ಮೂಲಕ ಆದೇಶಿಸಿ, ಅಂದರೆ ದೀರ್ಘಾವಧಿಯ ಸಂಸ್ಕರಣಾ ಸಮಯ ಹೊಂದಿರುವ ಕೆಲಸವು ಮೊದಲನೆಯದಾಗಿದೆ. ಈ ಅನುಕ್ರಮದಲ್ಲಿ ಪ್ರತಿಯೊಂದು ಕೆಲಸವನ್ನು ಪ್ರಸ್ತುತ ಲೋಡ್ (= ನಿಗದಿತ ಉದ್ಯೋಗಗಳ ಒಟ್ಟು ಸಂಸ್ಕರಣಾ ಸಮಯ) ಚಿಕ್ಕದಾದ ಯಂತ್ರವಾಗಿ ನಿಗದಿಪಡಿಸಿ. ಅಲ್ಗಾರಿದಮ್ನ ಹಂತ 2 ಮೂಲಭೂತವಾಗಿ ಪಟ್ಟಿ-ವೇಳಾಪಟ್ಟಿ (ಎಲ್ಎಸ್) ಅಲ್ಗಾರಿದಮ್ ಆಗಿದೆ. ವ್ಯತ್ಯಾಸವೇನೆಂದರೆ, ಎಲ್ಎಸ್ ಲೂಪ್ಗಳು ಉದ್ಯೋಗಗಳ ಮೇಲೆ ಅನಿಯಂತ್ರಿತ ಕ್ರಮದಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತವೆ, ಆದರೆ ಎಲ್ಪಿಟಿ ಪ್ರಕ್ರಿಯೆಯ ಸಮಯವನ್ನು ಇಳಿಸುವ ಮೂಲಕ ಅವುಗಳನ್ನು ಪೂರ್ವ-ಆದೇಶಿಸುತ್ತದೆ. ಎಲ್ಪಿಟಿಯನ್ನು ಮೊದಲ ಬಾರಿಗೆ 1960ರ ದಶಕದಲ್ಲಿ ರೊನಾಲ್ಡ್ ಗ್ರಹಾಂ ಅವರು ಒಂದೇ ರೀತಿಯ ಯಂತ್ರಗಳ ವೇಳಾಪಟ್ಟಿ ಸಮಸ್ಯೆಯ ಸಂದರ್ಭದಲ್ಲಿ ವಿಶ್ಲೇಷಿಸಿದರು. ನಂತರ, ಇದನ್ನು ಸಮಸ್ಯೆಯ ಇತರ ಅನೇಕ ರೂಪಾಂತರಗಳಿಗೆ ಅನ್ವಯಿಸಲಾಯಿತು. ಎಲ್ಪಿಟಿಯನ್ನು ಹೆಚ್ಚು ಅಮೂರ್ತ ರೀತಿಯಲ್ಲಿ, ಬಹುಮಾರ್ಗ ಸಂಖ್ಯೆ ವಿಭಜನೆಯ ಕ್ರಮಾವಳಿ ಎಂದು ವಿವರಿಸಬಹುದು. ಇನ್ಪುಟ್ ಸಂಖ್ಯೆಗಳ ಒಂದು ಸೆಟ್ S ಆಗಿದೆ, ಮತ್ತು ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕ m ಆಗಿದೆ; ಔಟ್ಪುಟ್ S ಅನ್ನು m ಉಪಗುಂಪುಗಳಾಗಿ ವಿಂಗಡಿಸುತ್ತದೆ. ಎಲ್ಪಿಟಿ ಅತಿದೊಡ್ಡದಿಂದ ಚಿಕ್ಕದಕ್ಕೆ ಇನ್ಪುಟ್ ಅನ್ನು ಆದೇಶಿಸುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ಇನ್ಪುಟ್ ಅನ್ನು ಇಲ್ಲಿಯವರೆಗಿನ ಚಿಕ್ಕ ಮೊತ್ತದೊಂದಿಗೆ ಭಾಗವಾಗಿ ಇರಿಸುತ್ತದೆ. ಇನ್ಪುಟ್ ಸೆಟ್ S = {4,5,6,7,8} ಮತ್ತು m = 2 ಆಗಿದ್ದರೆ, ಫಲಿತಾಂಶದ ವಿಭಾಗವು {8,5,4}, {7,6} ಆಗಿರುತ್ತದೆ. m = 3 ಆಗಿದ್ದರೆ, ಪರಿಣಾಮವಾಗಿ ಬರುವ 3-ಮಾರ್ಗದ ವಿಭಜನೆಯು {8}, {7,4}, {6,5} ಆಗಿರುತ್ತದೆ. ಗುಣಲಕ್ಷಣಗಳು LPT ಸೂಕ್ತವಾದ ವಿಭಾಗವನ್ನು ಕಂಡುಹಿಡಿಯದಿರಬಹುದು. ಉದಾಹರಣೆಗೆ, ಮೇಲಿನ ನಿದರ್ಶನದಲ್ಲಿ ಸೂಕ್ತವಾದ ವಿಭಜನೆ {8,7}, {6,5,4}, ಅಲ್ಲಿ ಎರಡೂ ಮೊತ್ತಗಳು 15ಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಅದರ ಉಪ-ಆಪ್ಟಿಮಾಲಿಟಿ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಮತ್ತು ಸರಾಸರಿ ಸಂದರ್ಭದಲ್ಲಿ ಎರಡಕ್ಕೂ ಸೀಮಿತವಾಗಿದೆ; ಕೆಳಗಿನ ಕಾರ್ಯಕ್ಷಮತೆಯ ಖಾತರಿಗಳನ್ನು ನೋಡಿ. ಎಲ್ಪಿಟಿಯ ಚಾಲನೆಯಲ್ಲಿರುವ ಸಮಯವು ವಿಂಗಡಣೆಯಿಂದ ಪ್ರಾಬಲ್ಯ ಹೊಂದಿದೆ, ಇದು ಒ (ಎನ್ ಲಾಗ್ ಎನ್) ಸಮಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಅಲ್ಲಿ ಎನ್ ಇನ್ಪುಟ್ಗಳ ಸಂಖ್ಯೆ. ಕಾರ್ಯಕ್ಷಮತೆಯ ಖಾತರಿಃ ಒಂದೇ ರೀತಿಯ ಯಂತ್ರಗಳನ್ನು ಒಂದೇ ರೀತಿಯ ಯಂತ್ರಗಳ ವೇಳಾಪಟ್ಟಿಗೆ ಬಳಸಿದಾಗ, ಎಲ್ಪಿಟಿಯು ಈ ಕೆಳಗಿನ ಅಂದಾಜು ಅನುಪಾತಗಳನ್ನು ಸಾಧಿಸುತ್ತದೆ. ಅತ್ಯಂತ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, ದುರಾಸೆಯ ವಿಭಾಗದಲ್ಲಿನ ಅತಿದೊಡ್ಡ ಮೊತ್ತವು ಹೆಚ್ಚಿನ ಸಮಯಗಳಲ್ಲಿ ಅತ್ಯುತ್ತಮವಾದ (ಕನಿಷ್ಠ) ಅತಿದೊಡ್ಡ ಮೊತ್ತವಾಗಿರುತ್ತದೆ. ಹೆಚ್ಚು ವಿವರವಾದ ವಿಶ್ಲೇಷಣೆಯು ಅತ್ಯುತ್ತಮ (ಕನಿಷ್ಠ) ಅತಿದೊಡ್ಡ ಮೊತ್ತದ ಒಂದು ಅಂಶವನ್ನು ನೀಡುತ್ತದೆ. (ಉದಾಹರಣೆಗೆ, m = 2 ಆಗಿರುವಾಗ ಈ ಅನುಪಾತವು). ಅಂಶವು ಬಿಗಿಯಾಗಿರುತ್ತದೆ. ಇನ್ಪುಟ್ಗಳಿವೆ ಎಂದು ಭಾವಿಸೋಣಃ ನಂತರ ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ ಹಿಂತಿರುಗುತ್ತದೆಃ,. ಗರಿಷ್ಠದೊಂದಿಗೆ, ಆದರೆ ಅತ್ಯುತ್ತಮ ವಿಭಾಗವೆಂದರೆಃ. ಗರಿಷ್ಠದೊಂದಿಗೆ. ಇನ್ಪುಟ್ ಪರಿಗಣನೆ ಇನ್ನೂ ಹೆಚ್ಚು ವಿವರವಾದ ವಿಶ್ಲೇಷಣೆಯು ಗರಿಷ್ಠ-ಮೊತ್ತದ ಭಾಗದಲ್ಲಿನ ಇನ್ಪುಟ್ಗಳ ಸಂಖ್ಯೆಯನ್ನು ಗಣನೆಗೆ ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ. ದುರಾಸೆಯ ವಿಭಜನೆಯ ಪ್ರತಿಯೊಂದು ಭಾಗದಲ್ಲೂ, ಜೆ-ನೇ ಅತಿ ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ. ದುರಾಸೆಯ ಭಾಗವಾದ ಪಿ ಯಲ್ಲಿ ಗರಿಷ್ಠ ಮೊತ್ತದೊಂದಿಗೆ, ಎಲ್ ಇನ್ಪುಟ್ಗಳಿವೆ ಎಂದು ಭಾವಿಸೋಣ. ನಂತರ, ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ನ ಅಂದಾಜು ಅನುಪಾತವು. ಇದು L ≤ 3 ಗೆ ಬಿಗಿಯಾಗಿರುತ್ತದೆ (L = 3 ಗೆ, ನಾವು ಸಾಮಾನ್ಯ ಅಂಶವನ್ನು ಪಡೆಯುತ್ತೇವೆ). ಪುರಾವೆ. ಪಿ ನಲ್ಲಿರುವ ಸಂಖ್ಯೆಗಳನ್ನು x1,., xL ನಿಂದ ಸೂಚಿಸಿ. ಪಿಗೆ xL ಅನ್ನು ಸೇರಿಸುವ ಮೊದಲು, ಅದರ ಮೊತ್ತವು ಚಿಕ್ಕದಾಗಿತ್ತು. ಆದ್ದರಿಂದ, ಪ್ರತಿ ಭಾಗದ ಸರಾಸರಿ ಮೊತ್ತವು ಕನಿಷ್ಠ x1 +. + xL-1 + xL/m ಆಗಿರುತ್ತದೆ. ಗರಿಷ್ಠ ಗರಿಷ್ಠ ಮೊತ್ತವು ಕನಿಷ್ಠ ಸರಾಸರಿ ಮೊತ್ತವಾಗಿರಬೇಕು. ಇದಕ್ಕೆ ವಿರುದ್ಧವಾಗಿ, ದುರಾಸೆಯ ಮೊತ್ತವು x1 +. + xL-1 + xL ಆಗಿದೆ. ಆದ್ದರಿಂದ ವ್ಯತ್ಯಾಸವು ಗರಿಷ್ಠ (1-1/ಮೀ) xL ಆಗಿರುತ್ತದೆ, ಇದು (1) ನಿಂದ ಗರಿಷ್ಠ (1-1/ಮೀ) * ಒಪಿಟಿ/ಎಲ್ ಆಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ಅನುಪಾತವು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ (1 + 1/L-1/Lm). ಅತ್ಯಂತ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ, ಹಿಂತಿರುಗಿಸಲಾದ ವಿಭಾಗದಲ್ಲಿನ ಚಿಕ್ಕ ಮೊತ್ತವು ಕನಿಷ್ಠ ಅತ್ಯುತ್ತಮ (ಗರಿಷ್ಠ) ಚಿಕ್ಕ ಮೊತ್ತದ ಪಟ್ಟು ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ಪುರಾವೆ-ಪುರಾವೆಯು ವಿರೋಧಾಭಾಸದಿಂದ ಕೂಡಿದೆ. ನಾವು ಕನಿಷ್ಠ ಪ್ರತಿ-ಉದಾಹರಣೆಯನ್ನು ಪರಿಗಣಿಸುತ್ತೇವೆ, ಅಂದರೆ, ಚಿಕ್ಕ m ಮತ್ತು ಕಡಿಮೆ ಇನ್ಪುಟ್ ಸಂಖ್ಯೆಗಳೊಂದಿಗೆ ಪ್ರತಿ-ಉದಾಹರಣೆ. ದುರಾಸೆಯ ವಿಭಾಗವನ್ನು P1,., Pm ನಿಂದ ಮತ್ತು ಅತ್ಯುತ್ತಮ ವಿಭಾಗವನ್ನು Q1,., Qm ನಿಂದ ಸೂಚಿಸಿ. ಕನಿಷ್ಠ ಪ್ರತಿ-ಉದಾಹರಣೆಯ ಕೆಲವು ಗುಣಲಕ್ಷಣಗಳೆಂದರೆಃ ಅತ್ಯುತ್ತಮ ವಿಭಾಗದಲ್ಲಿನ ಕನಿಷ್ಠ-ಮೊತ್ತವು 4 ಆಗಿದೆ, ಮತ್ತು ದುರಾಸೆಯ ವಿಭಾಗದಲ್ಲಿನ ಕನಿಷ್ಠ-ಮೊತ್ತವು 3ಕ್ಕಿಂತ ಕಡಿಮೆಯಾಗಿದೆ (ಇದು ಕೇವಲ ಸಾಮಾನ್ಯೀಕರಣವಾಗಿದೆ-ಇದು ಸಾಮಾನ್ಯತೆಯ ನಷ್ಟವಿಲ್ಲದೆ). ದುರಾಸೆಯ ವಿಭಾಗದಲ್ಲಿನ ಗರಿಷ್ಠ ಮೊತ್ತವು 4 ಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ (ಏಕೆಂದರೆ ಎರಡೂ ವಿಭಾಗಗಳಲ್ಲಿನ ಒಟ್ಟು ಮೊತ್ತವು ಒಂದೇ ಆಗಿರುತ್ತದೆ ಮತ್ತು ಇದು ಕನಿಷ್ಠ 4 ಮೀ ಆಗಿರುತ್ತದೆ). ಕೆಲವು ದುರಾಸೆಯ ಬಿನ್ ಪೈಗೆ ಮೊತ್ತ (ಪಿಐ) 3 ಆಗಿದ್ದರೆ, ಪಿಐ ಯಾವುದೇ ಅತ್ಯುತ್ತಮ ಬಿನ್ ಕ್ಯೂಜೆಯಿಂದ ಪ್ರಾಬಲ್ಯ ಹೊಂದಿರುವುದಿಲ್ಲ. ಪುರಾವೆಃ ಪೈ ಮೇಲೆ ಕ್ಯೂಜೆ ಪ್ರಾಬಲ್ಯ ಹೊಂದಿದ್ದರೆ, ನಾವು ಎಂ ಅನ್ನು ಎಂ-1 ಗೆ ಕಡಿಮೆ ಮಾಡುವ ಮೂಲಕ ಮತ್ತು ಪೈ ನಲ್ಲಿರುವ ವಸ್ತುಗಳನ್ನು ತೆಗೆದುಹಾಕುವ ಮೂಲಕ ಸಣ್ಣ ಪ್ರತಿ-ಉದಾಹರಣೆಯನ್ನು ರಚಿಸಬಹುದು. ದುರಾಸೆಯ ವಿಭಾಗದಲ್ಲಿನ ಕನಿಷ್ಠ ಮೊತ್ತವು 3ಕ್ಕಿಂತ ಕಡಿಮೆಯಿರುತ್ತದೆ. ಆಪ್ಟಿಮಲ್ ವಿಭಜನೆಯಲ್ಲಿ, ಪೈ ನಲ್ಲಿರುವ ವಸ್ತುಗಳನ್ನು ಕ್ಯೂಜೆಯಲ್ಲಿ ಅವುಗಳ ಪ್ರಾಬಲ್ಯದ ವಸ್ತುಗಳಿಂದ ಬದಲಾಯಿಸಬಹುದು, ಆದ್ದರಿಂದ ಕನಿಷ್ಠ-ಮೊತ್ತವು ಕನಿಷ್ಠ 4 ಆಗಿರುತ್ತದೆ. ಕೆಲವು ದುರಾಸೆಯ ಬಿನ್ ಪೈಗೆ ಮೊತ್ತ (ಪಿಐ) 3 ಆಗಿದ್ದರೆ, ಪಿಐ ಕನಿಷ್ಠ ಎರಡು ಸಂಖ್ಯೆಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಪುರಾವೆಃ ಪೈ ಕೇವಲ ಒಂದು ಸಂಖ್ಯೆ x ಅನ್ನು ಹೊಂದಿದ್ದರೆ, ಅದು x.givese ಅನ್ನು ಹೊಂದಿರುವ ಆಪ್ಟಿಮಲ್ ಬಿನ್ ಕ್ಯೂಜಿಯಿಂದ ಪ್ರಾಬಲ್ಯ ಹೊಂದಿದೆ, ಕೆಲವು ಇನ್ಪುಟ್ x ಕನಿಷ್ಠ 3 ಆಗಿದೆ, ಮತ್ತು ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ ಅದನ್ನು ಕೆಲವು ಪೈನಲ್ಲಿ ಇರಿಸುತ್ತದೆ. ನಂತರ, 3 ಕ್ಕಿಂತ ಕಡಿಮೆ ಮೊತ್ತದ ಬಂಡಲ್ ಇರುವುದರಿಂದ, ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ ಹಿಂದಿನ ಲೆಮ್ಮಾವನ್ನು ವಿರೋಧಿಸುವ ಯಾವುದೇ ಇನ್ಪುಟ್ ಅನ್ನು ಪೈನಲ್ಲಿ ಇಡುವುದಿಲ್ಲ. ಪ್ರತಿ ದುರಾಸೆಯ ಬಿನ್ ಪೈ ಗರಿಷ್ಠ ಒಂದು ಇನ್ಪುಟ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ-3/2 ಕ್ಕಿಂತ ದುರ್ಬಲವಾಗಿ ದೊಡ್ಡದಾಗಿದೆ. ಪುರಾವೆಃ ಪೈ ಅಂತಹ ಎರಡು ಇನ್ಪುಟ್ಗಳನ್ನು ನಿಗದಿಪಡಿಸಿದ ಮೊದಲ ದುರಾಸೆಯ ಬಿನ್ ಆಗಿರಲಿ. ಇನ್ಪುಟ್ಗಳನ್ನು ಅವರೋಹಣ ಕ್ರಮದಲ್ಲಿ ನಿಗದಿಪಡಿಸಲಾಗಿರುವುದರಿಂದ, ಪೈ ಎರಡು ಇನ್ಪುಟ್ಗಳನ್ನು ನಿಗದಿಪಡಿಸಿದ ಮೊದಲ ದುರಾಸೆಯ ಬಿನ್ ಆಗಿದೆ. ಇದರರ್ಥ ಇದು ಅತಿದೊಡ್ಡ m + 1 ಇನ್ಪುಟ್ಗಳಲ್ಲಿ ಚಿಕ್ಕದಾದ ಎರಡು ಇನ್ಪುಟ್ಗಳನ್ನು ಹೊಂದಿರಬೇಕು. ಇದಲ್ಲದೆ, ಈ ಎರಡು ವಸ್ತುಗಳ ಮೊತ್ತವು ಕನಿಷ್ಠ 3/2+3 2 = 3 ಆಗಿರುವುದರಿಂದ, ಪೈಗೆ ಬೇರೆ ಯಾವುದೇ ಇನ್ಪುಟ್ ಅನ್ನು ನಿಗದಿಪಡಿಸಲಾಗಿಲ್ಲ. ಮತ್ತೊಂದೆಡೆ, ಪಾರಿವಾಳದ ರಂಧ್ರದ ತತ್ವದ ಪ್ರಕಾರ, ಕೆಲವು ಸೂಕ್ತವಾದ ಬಿನ್ ಕ್ಯೂಜೆ ಇರಬೇಕು, ಅದು ಅತಿದೊಡ್ಡ ಎಂ + 1 ಇನ್ಪುಟ್ಗಳಲ್ಲಿ ಕೆಲವು ಎರಡು ಇನ್ಪುಟ್ಗಳನ್ನು ಹೊಂದಿರಬೇಕು; ಆದ್ದರಿಂದ ಪಿಐನಲ್ಲಿ ಕ್ಯೂಜೆ ಪ್ರಾಬಲ್ಯ ಹೊಂದಿದೆ. ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ನ ಚಾಲನೆಯ ಸಮಯದಲ್ಲಿ, ಯಾವುದೇ ಬಿನ್ನ ಮೊತ್ತವು 4 ಅನ್ನು ಮೀರುವ ಮೊದಲು ಪ್ರತಿ ಬಿನ್ ಪಿಯಲ್ಲಿನ ಮೊತ್ತವು ಕನಿಷ್ಠ 8/3 ಆಗುತ್ತದೆ. ಪುರಾವೆಃ ಕೆಲವು ಬಿನ್ ಪೈಗೆ ಸೇರಿಸಲಾದ ಮೊದಲ ಇನ್ಪುಟ್ y ಆಗಿರಲಿ, ಅದು ಅದರ ಮೊತ್ತವನ್ನು 4 ಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿಸಿತು. y ಅನ್ನು ಸೇರಿಸುವ ಮೊದಲು, ಪೈ ಅತ್ಯಂತ ಚಿಕ್ಕ ಮೊತ್ತವನ್ನು ಹೊಂದಿತ್ತು, ಇದು ಊಹೆಯ ಪ್ರಕಾರ 8/3 ಗಿಂತ ಚಿಕ್ಕದಾಗಿದೆ; ಇದರರ್ಥ y> 4/3. ಮೊದಲನೆಯದರ ಕೆಳಗಿನಿಂದ y ವರೆಗಿನ ಎಲ್ಲಾ ಇನ್ಪುಟ್ಗಳ ಗುಂಪನ್ನು T ಸೂಚಿಸೋಣ; ಈ ಎಲ್ಲಾ ಇನ್ಪುಟ್ಗಳು 4/3 ಗಿಂತ ದೊಡ್ಡದಾಗಿರುತ್ತವೆ. ಪೈ 8/3 ಗಿಂತ ಚಿಕ್ಕದಾಗಿರುವುದರಿಂದ, ಅದು ಟಿ ಯಿಂದ ನಿಖರವಾಗಿ ಒಂದು ಐಟಂ x ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ಈಗ ಪೈ ನಿಖರವಾಗಿ 2 ಐಟಂಗಳನ್ನು {x, y} ಹೊಂದಿದೆ, ಮತ್ತು ಅಲ್ಗಾರಿದಮ್ ಕೊನೆಗೊಳ್ಳುವವರೆಗೆ ಈ 2 ಐಟಂಗಳೊಂದಿಗೆ ಉಳಿಯುತ್ತದೆ. m ಮೊದಲನೆಯದರಿಂದ x ವರೆಗಿನ ಅಂಶಗಳ ಸಂಖ್ಯೆಯಾಗಿರಲಿ. ನಾವು ಈಗ ಎರಡು ರೀತಿಯಲ್ಲಿ ವಸ್ತುಗಳನ್ನು ಟಿ ಯಲ್ಲಿ ಎಣಿಸುವ ಮೂಲಕ ವಿರೋಧಾಭಾಸವನ್ನು ತೋರಿಸುತ್ತೇವೆ. ಮೊದಲಿಗೆ, ಸೂಕ್ತವಾದ ತೊಟ್ಟಿಗಳನ್ನು ಪರಿಗಣಿಸಿ. ಅಂತಹ ಯಾವುದೇ ಬಿನ್ ಕನಿಷ್ಠ x ನಷ್ಟು ದೊಡ್ಡದಾದ ವಸ್ತುವನ್ನು ಹೊಂದಿದ್ದರೆ, ಅದು T ಯ ಯಾವುದೇ ವಸ್ತುವನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ, ಇಲ್ಲದಿದ್ದರೆ ಅದು {x, y} ಅನ್ನು ನಿಯಂತ್ರಿಸುತ್ತದೆ. ಇದಲ್ಲದೆ, ಅಂತಹ ಯಾವುದೇ ಬಿನ್ ಟಿ ಯಿಂದ ಮೂರು ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರಬಾರದು, ಏಕೆಂದರೆ ಅವುಗಳಲ್ಲಿ ಯಾವುದೇ ಎರಡರ ಮೊತ್ತವು 8/3 ಗಿಂತ ದೊಡ್ಡದಾಗಿದೆ, ಇದು x ಗಿಂತ ದೊಡ್ಡದಾಗಿದೆ; ಮತ್ತು ಮೂರನೆಯದು ಕನಿಷ್ಠ y ಆಗಿದೆ, ಆದ್ದರಿಂದ ಇದು {x, y} ಅನ್ನು ನಿಯಂತ್ರಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ, Tಯಲ್ಲಿನ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ 1 * m + 2 * (n-m) = 2n-m ಆಗಿರುತ್ತದೆ. x ಅನ್ನು ಹೊಂದಿರುವ ಬಂಡಲ್ಗೆ y ಅನ್ನು ಸೇರಿಸಿದಾಗ, ಅದು ಚಿಕ್ಕ ಮೊತ್ತವನ್ನು ಹೊಂದಿರುವ ಬಂಡಲ್ ಆಗಿದೆ. ಆದ್ದರಿಂದ, x ಗಿಂತ ಚಿಕ್ಕದಾದ T ಯ ಎಲ್ಲಾ ಅಂಶಗಳು ಕನಿಷ್ಠ ಒಂದು T ಯ ಇತರ ವಸ್ತುವಿನೊಂದಿಗೆ ದುರಾಸೆಯ ಡಬ್ಬಿಯಲ್ಲಿರಬೇಕು. ಆದ್ದರಿಂದ, ಟಿ ನಲ್ಲಿನ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯು ಕನಿಷ್ಠ (m-1) + 2 * (n-m + 1) = 2n-m + 1-ವಿರೋಧಾಭಾಸವಾಗಿದೆ. ಸಾಮಾನ್ಯತೆಯನ್ನು ಕಳೆದುಕೊಳ್ಳದೆ, ಎಲ್ಲಾ ಇನ್ಪುಟ್ಗಳು 1/3 ಕ್ಕಿಂತ ಚಿಕ್ಕದಾಗಿದೆ ಅಥವಾ ಕನಿಷ್ಠ 1 ಎಂದು ನಾವು ಊಹಿಸಬಹುದು. ಪುರಾವೆಃ ಕೆಲವು ಇನ್ಪುಟ್ x (1/3,1) ನಲ್ಲಿದೆ ಎಂದು ಭಾವಿಸೋಣ. ನಾವು x ಅನ್ನು 1 ರಿಂದ ಬದಲಾಯಿಸುತ್ತೇವೆ. ಇದು ನಿಸ್ಸಂಶಯವಾಗಿ ಅತ್ಯುತ್ತಮ ಕನಿಷ್ಠ ಮೊತ್ತವನ್ನು ಕಡಿಮೆ ಮಾಡುವುದಿಲ್ಲ. ಇದು ದುರಾಸೆಯ ಕನಿಷ್ಠ ಮೊತ್ತವನ್ನು ಬದಲಾಯಿಸುವುದಿಲ್ಲ ಎಂದು ನಾವು ತೋರಿಸುತ್ತೇವೆ. ಕೆಲವು ದುರಾಸೆಯ ಬಂಡಲ್ ಪೈ 4 ಕ್ಕಿಂತ ದೊಡ್ಡ ಮೊತ್ತವನ್ನು ಹೊಂದಿದೆ ಎಂದು ನಮಗೆ ತಿಳಿದಿದೆ. ಕೊನೆಯ ಇನ್ಪುಟ್ ಅನ್ನು ಪೈಗೆ ಸೇರಿಸುವ ಮೊದಲು, ಅದರ ಮೊತ್ತವು 3 ಕ್ಕಿಂತ ಚಿಕ್ಕದಾಗಿತ್ತು; ಆದ್ದರಿಂದ 1 ಕ್ಕಿಂತ ದೊಡ್ಡ ಇನ್ಪುಟ್ ಅನ್ನು ಸೇರಿಸಿದಾಗ ಪೈ 4 ಕ್ಕಿಂತ ದೊಡ್ಡದಾಯಿತು. ಹಿಂದಿನ ಲೆಮ್ಮಾದ ಹೊತ್ತಿಗೆ, ಆ ಸಮಯದಲ್ಲಿ ಇತರ ಎಲ್ಲಾ ದುರಾಸೆಯ ಕಟ್ಟುಗಳ ಮೊತ್ತವು ಕನಿಷ್ಠ 8/3 ಆಗಿತ್ತು. ಅಲ್ಗಾರಿದಮ್ ನಂತರ x ಗೆ ಬರುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಕೆಲವು ಬಿನ್ ಪಿಜೆಗೆ x ಅನ್ನು ಸೇರಿಸಿದ ನಂತರ, ಪಿಜೆ ಮೊತ್ತವು ಕನಿಷ್ಠ 8/3+1 3 = 3 ಆಗುತ್ತದೆ, ಆದ್ದರಿಂದ ಹೆಚ್ಚಿನ ವಸ್ತುಗಳನ್ನು ಪಿಜೆಗೆ ಸೇರಿಸಲಾಗುವುದಿಲ್ಲ. ಆದ್ದರಿಂದ Pj ಯು [1/3,1) ನಲ್ಲಿ ಗಾತ್ರದೊಂದಿಗೆ ಕೇವಲ ಒಂದು ಇನ್ಪುಟ್ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಒಮ್ಮೆ x ಅನ್ನು 1 ರಿಂದ ಬದಲಾಯಿಸಿದ ನಂತರ, ಅದನ್ನು ಇನ್ನೂ Pj ಗೆ ಸೇರಿಸಲಾಗುತ್ತದೆ ಮತ್ತು ಅದರ ಮೊತ್ತವು ಇನ್ನೂ 3 ಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ ದುರಾಸೆಯ ಕನಿಷ್ಠ ಮೊತ್ತವು ಬದಲಾಗುವುದಿಲ್ಲ. ನಾವು ಈಗ ಇನ್ಪುಟ್ಗಳನ್ನು ಸಣ್ಣ (1/3 ಕ್ಕಿಂತ ಕಡಿಮೆ) ಮತ್ತು ದೊಡ್ಡ (ಕನಿಷ್ಠ 1) ಎಂದು ವಿಂಗಡಿಸಬಹುದು. ಪೈ ನಲ್ಲಿರುವ ಸಣ್ಣ ವಸ್ತುಗಳ ಗುಂಪನ್ನು ಸಿ ಎಂದು ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ಸಂಸ್ಕರಿಸಲು ಪ್ರಾರಂಭಿಸಿದಾಗ, ಎಲ್ಲಾ ಕಟ್ಟುಗಳಲ್ಲಿನ ಮೊತ್ತವು ಕನಿಷ್ಠ 8/3 ಆಗಿರುತ್ತದೆ ಎಂಬುದನ್ನು ಗಮನಿಸಿ. ಕನಿಷ್ಠ ಪ್ರತಿರೂಪವು ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲ ಎಂಬುದಕ್ಕೆ ಪುರಾವೆಯು ತೂಕದ ಯೋಜನೆಯನ್ನು ಬಳಸುತ್ತದೆ. ಪ್ರತಿ ಇನ್ಪುಟ್ x ಗೆ ಅದರ ಗಾತ್ರ ಮತ್ತು ದುರಾಸೆಯ ಬಂಡಲ್ ಪ್ರಕಾರ ತೂಕವನ್ನು w (x) ನಿಗದಿಪಡಿಸಲಾಗಿದೆಃ x ಒಂದು ದೊಡ್ಡ ವಸ್ತುವಾಗಿದ್ದರೆಃ x ಎಂಬುದು ಪೈ ನಲ್ಲಿರುವ ಏಕೈಕ ದೊಡ್ಡ ವಸ್ತುವಾಗಿದ್ದರೆ, ನಂತರ w (x) = 8/3 ಆಗಿರುತ್ತದೆ. ಪೈ ನಿಖರವಾಗಿ ಎರಡು ವಸ್ತುಗಳನ್ನು {x, y} ಹೊಂದಿದ್ದರೆ ಮತ್ತು ಎರಡೂ ದೊಡ್ಡದಾಗಿದ್ದರೆ, ಮತ್ತು x> y, ಮತ್ತು ಮೊತ್ತ (ಪೈ) ≤3 ಆಗಿದ್ದರೆ, ನಂತರ w (x) = 8/3 ಆಗಿರುತ್ತದೆ. ಇಲ್ಲದಿದ್ದರೆ, w (x) = 4/3 ಆಗಿರುತ್ತದೆ. x ಒಂದು ಸಣ್ಣ ವಸ್ತುವಾಗಿದ್ದರೆಃ ಮೊತ್ತ (ಪೈ) ≤3 ಆಗಿದ್ದರೆ, ನಂತರ w (x) = 4x/(3 ಮೊತ್ತ (ಸಿ)); ಆದ್ದರಿಂದ w (ಸಿ) = 4/3. ಮೊತ್ತವು (ಪೈ) <3 ಆಗಿದ್ದರೆ, ನಂತರ ಡಬ್ಲ್ಯೂ (ಎಕ್ಸ್) = 2x/(3 ಮೊತ್ತ (ಸಿ)); ಆದ್ದರಿಂದ ಡಬ್ಲ್ಯೂ (ಸಿ) = 2/3. ಈ ತೂಕದ ಯೋಜನೆಯು ಈ ಕೆಳಗಿನ ಗುಣಲಕ್ಷಣಗಳನ್ನು ಹೊಂದಿದೆಃ x ≤2 ಆಗಿದ್ದರೆ, ನಂತರ w (x) = 8/3 ಆಗಿರುತ್ತದೆ. ಪುರಾವೆಃ x ದೊಡ್ಡದಾಗಿದೆ. ಅದು ಪೈ ನಲ್ಲಿದೆ ಎಂದು ಭಾವಿಸೋಣ. ಪೈ ಮತ್ತೊಂದು ದೊಡ್ಡ ಐಟಂ y ಅನ್ನು ಹೊಂದಿದ್ದರೆ, x + y ≤ 3 ಆದ್ದರಿಂದ ಪೈನಲ್ಲಿ ಬೇರೆ ಯಾವುದೇ ಐಟಂ ಇಲ್ಲ. ಇದಲ್ಲದೆ, x> y ಏಕೆಂದರೆ ಗರಿಷ್ಠ ಒಂದು ವಸ್ತುವು 3/2 ಗಿಂತ ದೊಡ್ಡದಾಗಿರುತ್ತದೆ. ಆದ್ದರಿಂದ w (x) = 8/3. x <1/3 ಆಗಿದ್ದರೆ, ನಂತರ w (x)> 2x. ಪುರಾವೆಃ x ಚಿಕ್ಕದಾಗಿದೆ. ಅದು ಪೈ ನಲ್ಲಿದೆ ಎಂದು ಭಾವಿಸೋಣ. ಮೊತ್ತವು (ಪಿಐ) 3 ಆಗಿದ್ದರೆ, ಅದಕ್ಕೆ x ಅನ್ನು ಸೇರಿಸುವ ಮೊದಲು ಮೊತ್ತವು (ಪಿಐ) 3ಕ್ಕಿಂತ ಚಿಕ್ಕದಾಗಿದ್ದ ಕಾರಣ, ಅದು ಈಗ 10/3 ಗಿಂತ ಚಿಕ್ಕದಾಗಿದೆ. ಆದರೆ ಅಲ್ಗಾರಿದಮ್ ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ಸಂಸ್ಕರಿಸಲು ಪ್ರಾರಂಭಿಸಿದಾಗ, ಮೊತ್ತ (ಪೈ) ಕನಿಷ್ಠ 8/3 ಆಗಿತ್ತು. ಇದರರ್ಥ ಮೊತ್ತ (ಸಿ) <2/3, ಆದ್ದರಿಂದ ಡಬ್ಲ್ಯೂ (ಎಕ್ಸ್) = 4x/(3 ಮೊತ್ತ (ಸಿ))> 2x. ಮೊತ್ತ (ಪೈ) <3 ಆಗಿದ್ದರೆ ಮೊತ್ತ (ಸಿ) <3-8/3 = 1/3, ಆದ್ದರಿಂದ ಡಬ್ಲ್ಯೂ (ಎಕ್ಸ್) = 2x/(3 ಮೊತ್ತ (ಸಿ))> 2x. ಪ್ರತಿ ದುರಾಸೆಯ ಬಿನ್ ಪೈನ ತೂಕವು ಗರಿಷ್ಠ 4 ಆಗಿರುತ್ತದೆ ಮತ್ತು ಕನಿಷ್ಠ ಒಂದು ದುರಾಸೆಯ ಬಿನ್ನ ತೂಕವು ಗರಿಷ್ಠ 10/3 ಆಗಿರುತ್ತದೆ. ಪುರಾವೆಃ ಪೈ ನಲ್ಲಿನ ಎಲ್ಲಾ ಇನ್ಪುಟ್ಗಳು ದೊಡ್ಡದಾಗಿದ್ದರೆ, ಅದು 8/3 ತೂಕದ ಒಂದೇ ಇನ್ಪುಟ್, 8/3+4 3 ತೂಕದ ಎರಡು ಇನ್ಪುಟ್ಗಳು ಅಥವಾ 4/3+4 3 + 4/3 ತೂಕದ ಮೂರು ಇನ್ಪುಟ್ಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಪೈ ನಲ್ಲಿನ ಕೆಲವು ಇನ್ಪುಟ್ಗಳು ಚಿಕ್ಕದಾಗಿದ್ದರೆ, ಅವುಗಳ ಒಟ್ಟು ತೂಕವು ಗರಿಷ್ಠ 3/4 ಆಗಿರುತ್ತದೆ. ಗರಿಷ್ಠ ಎರಡು ದೊಡ್ಡ ಇನ್ಪುಟ್ಗಳಿವೆ, ಮತ್ತು ಅವುಗಳ ತೂಕವು 8/3 ಅಥವಾ 4/3+4 3 ಆಗಿರುತ್ತದೆ. ಅಂತಿಮವಾಗಿ, 3ಕ್ಕಿಂತ ಕಡಿಮೆ ಮೊತ್ತವನ್ನು ಹೊಂದಿರುವ ದುರಾಸೆಯ ಡಬ್ಬಿಯ ತೂಕವು ಗರಿಷ್ಠ 8/3 (ಅದು ಕೇವಲ ದೊಡ್ಡ ಹೂಡಿಕೆಯನ್ನು ಹೊಂದಿದ್ದರೆ) ಅಥವಾ 10/3 (ಅದು ಕೆಲವು ಸಣ್ಣ ಹೂಡಿಕೆಯನ್ನು ಹೊಂದಿದ್ದರೆ) ಆಗಿರುತ್ತದೆ. ಪ್ರತಿ ಅತ್ಯುತ್ತಮ ಬಿನ್ ಕ್ಯೂಜೆಯ ತೂಕ ಕನಿಷ್ಠ 4 ಆಗಿರುತ್ತದೆ. ಪುರಾವೆಃ ಕ್ಯೂಜೆ ಕೇವಲ ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ಅವುಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದೂ ಡಬ್ಲ್ಯೂ (ಎಕ್ಸ್)> 2x ಅನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ, ಆದ್ದರಿಂದ ಡಬ್ಲ್ಯೂ (ಕ್ಯೂಜೆ)> 2 ಮೊತ್ತ (ಕ್ಯೂಜೆ) ≤ 8. ಕ್ಯೂಜೆ ನಿಖರವಾಗಿ ಒಂದು ದೊಡ್ಡ ಐಟಂ x ಅನ್ನು ಹೊಂದಿದ್ದರೆ, ಅದು ಕನಿಷ್ಠ 4-x ಮೊತ್ತ ಮತ್ತು ಕನಿಷ್ಠ 8-2x ತೂಕದ ಕೆಲವು ಸಣ್ಣ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರಬೇಕು. ನಂತರ, x <2 ಮತ್ತು ಸಣ್ಣ ವಸ್ತುಗಳ ತೂಕ ಕನಿಷ್ಠ 8-4 = 4, ಅಥವಾ x in (2,3) ಮತ್ತು w (x) = 8/3 ಆಗಿರುತ್ತದೆ ಮತ್ತು ಸಣ್ಣ ವಸ್ತುಗಳ ತೂಕ ಕನಿಷ್ಠ 8-6 = 2 ಆಗಿರುತ್ತದೆ. ಎರಡೂ ಸಂದರ್ಭಗಳಲ್ಲಿ ಒಟ್ಟು ತೂಕವು ಕನಿಷ್ಠ 4 ಆಗಿರುತ್ತದೆ. ಕ್ಯೂಜೆ ನಿಖರವಾಗಿ ಎರಡು ದೊಡ್ಡ ವಸ್ತುಗಳನ್ನು x> y ಮತ್ತು x ≤ 2 ಅನ್ನು ಹೊಂದಿದ್ದರೆ, ಕನಿಷ್ಠ 8/3+4 3 = 4 ಇರುತ್ತದೆ. x + y ≤ 10/3 ಆಗಿದ್ದರೆ, ಸಣ್ಣ ವಸ್ತುಗಳ ಮೊತ್ತವು ಕನಿಷ್ಠ 2/3 ಆಗಿರಬೇಕು, ಆದ್ದರಿಂದ ಒಟ್ಟು ತೂಕವು ಕನಿಷ್ಠ 4/3+4 3 + 2 * 2/3 = 4 ಆಗಿರುತ್ತದೆ. ಇಲ್ಲದಿದ್ದರೆ, x> 5/3. ಆದ್ದರಿಂದ ಕೆಲವು ದುರಾಸೆಯ ಬಿನ್ ಪಿಎಂನಲ್ಲಿ x ಮೊದಲ ಇನ್ಪುಟ್ ಆಗಿತ್ತು. ಪಿಎಮ್ಗೆ ಸೇರಿಸಲಾದ ಎರಡನೇ ಇನ್ಪುಟ್ z ಆಗಿರಲಿ. x + z ≤ 3 ಆಗಿದ್ದರೆ, Pm ನಲ್ಲಿ ಯಾವುದೇ ಇನ್ಪುಟ್ಗಳಿಲ್ಲ, ಆದ್ದರಿಂದ w (x) = 8/3 ಮತ್ತು ನಾವು ಮುಗಿಸಿದ್ದೇವೆ. ಇಲ್ಲದಿದ್ದರೆ, x + z <3 ಆಗಿರುತ್ತದೆ. ಕೆಲವು ದುರಾಸೆಯ ತೊಟ್ಟಿಗಳಲ್ಲಿ ಮೊತ್ತವು 4 ಅನ್ನು ಮೀರಿದ ಅತಿ ಚಿಕ್ಕ ಹೂಡಿಕೆಯು ವಿ ಆಗಿರಲಿ. x <8/3 ರಿಂದ, z ಅನ್ನು v ಗಿಂತ ಮೊದಲು ಸಂಸ್ಕರಿಸಿರಬೇಕು, ಆದ್ದರಿಂದ z ≤ v. ಈಗ ಕ್ಯೂಜೆಯಲ್ಲಿ ಯಾವುದೇ ಸಣ್ಣ ವಸ್ತುವನ್ನು ಪರಿಗಣಿಸಿ, ಮತ್ತು ಅದು ಯಾವುದೋ ದುರಾಸೆಯ ಬಿನ್ ಪೈನಲ್ಲಿದೆ ಎಂದು ಭಾವಿಸೋಣ. ಮೊತ್ತ (ಪೈ) <3 ಆಗಿದ್ದರೆ, ಪಿಯಲ್ಲಿ v ಅನ್ನು ಸೇರಿಸಲಾಗಿಲ್ಲ ಎಂಬ ಅಂಶವು v> 4-ಮೊತ್ತ (ದೊಡ್ಡ-ಐಟಂಗಳು-ಇನ್-ಪೈ)> 1 + ಮೊತ್ತ (ಸಣ್ಣ-ಐಟಂಗಳು-ಇನ್-ಪೈ) ಎಂದು ಸೂಚಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ, 1 + ಮೊತ್ತ (ಸಿ) + x <v + x ≤ z + x <3 ಮತ್ತು ಮೊತ್ತ (ಸಿ) <2-x. ಇದರರ್ಥ 2 * ಮೊತ್ತ (ಸಿ) <4-4x ≤ 4-x-y ≤ ಮೊತ್ತ (ಸಣ್ಣ-ವಸ್ತುಗಳು-ಇನ್-ಕ್ಯೂಜೆ). ಆದ್ದರಿಂದ w (t) = 2t/(3sum (Si))> 4t/(3sum (ಸಣ್ಣ-ವಸ್ತುಗಳು-ಇನ್-ಕ್ಯೂಜೆ)). ಮೊತ್ತವು (ಪೈ) 3, ಮತ್ತು ಮೊತ್ತವು (ಸಿ) ≤ 1 ಆಗಿದ್ದರೆ, ನಂತರ ಡಬ್ಲ್ಯೂ (ಟಿ) = 4/3 ಮತ್ತು ನಾವು ಮುಗಿಸಿದ್ದೇವೆ. t ಅನ್ನು ಸೇರಿಸುವ ಮೊದಲು ಮೊತ್ತ (ಪೈ) 3 ಕ್ಕಿಂತ ಕಡಿಮೆಯಿರುವುದರಿಂದ, ಮೊತ್ತ (ಪೈ) <3 + ಮೊತ್ತ (ಸಿ)/2 ಆಗಿದೆ. ಪಿಯಲ್ಲಿ v ಅನ್ನು ಸೇರಿಸಲಾಗಿಲ್ಲ ಎಂಬ ಅಂಶವು v> 4-ಮೊತ್ತ (ದೊಡ್ಡ-ಐಟಂಗಳು-ಇನ್-ಪೈ)> 1 + ಮೊತ್ತ (ಸಣ್ಣ-ಐಟಂಗಳು-ಇನ್-ಪೈ)/2 ಎಂದು ಸೂಚಿಸುತ್ತದೆ. ಹಿಂದಿನ ಪ್ಯಾರಾಗ್ರಾಫ್ಗೆ ಹೋಲಿಕೆ, ಡಬ್ಲ್ಯೂ (ಟಿ)> 4 ಟಿ/(3sum (ಸಣ್ಣ-ವಸ್ತುಗಳು-ಇನ್-ಕ್ಯೂಜೆ)). ಆದ್ದರಿಂದ, ಕ್ಯೂಜೆಯಲ್ಲಿನ ಎಲ್ಲಾ ಸಣ್ಣ ವಸ್ತುಗಳ ಒಟ್ಟು ತೂಕವು ಕನಿಷ್ಠ 3/4 ಆಗಿರುತ್ತದೆ, ಆದ್ದರಿಂದ ಕ್ಯೂಜೆಯ ಒಟ್ಟು ತೂಕವು ಕನಿಷ್ಠ 4/3+10 3> 4 ಆಗಿರುತ್ತದೆ. ಕ್ಯೂಜೆ ನಿಖರವಾಗಿ ಮೂರು ಅಥವಾ ಹೆಚ್ಚಿನ ದೊಡ್ಡ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿದ್ದರೆ, ಅದರ ಒಟ್ಟು ತೂಕ ಕನಿಷ್ಠ 4/3+4 3 + 4/3 = 4 ಆಗಿರುತ್ತದೆ. ಕೊನೆಯ ಎರಡು ಸಮರ್ಥನೆಗಳು ವಿರೋಧಾತ್ಮಕವಾಗಿವೆ, ಏಕೆಂದರೆ ಮೊದಲನೆಯದು ಎಲ್ಲಾ ಇನ್ಪುಟ್ಗಳ ತೂಕವು ಗರಿಷ್ಠ 4 ಮೀ-2/3 ಎಂದು ಸೂಚಿಸುತ್ತದೆ, ಮತ್ತು ಎರಡನೆಯದು ಎಲ್ಲಾ ಇನ್ಪುಟ್ಗಳ ತೂಕವು ಕನಿಷ್ಠ 4 ಮೀ ಎಂದು ಸೂಚಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ, ಇದಕ್ಕೆ ವಿರುದ್ಧವಾದ ಉದಾಹರಣೆ ಅಸ್ತಿತ್ವದಲ್ಲಿಲ್ಲ. ಅನುಪಾತದ ಮೇಲಿನ ಮಿತಿಯು ಹೆಚ್ಚು ಅತ್ಯಾಧುನಿಕವಾದ ವಿಶ್ಲೇಷಣೆಯು ಅನುಪಾತವು ಗರಿಷ್ಠವಾಗಿದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ (ಉದಾಹರಣೆಗೆ, m = 2 ಆಗಿದ್ದರೆ ಅನುಪಾತವು 5/6 ಆಗಿರುತ್ತದೆ). ಬಿಗಿತ ಮತ್ತು ಉದಾಹರಣೆ ಮೇಲಿನ ಅನುಪಾತವು ಬಿಗಿಯಾಗಿದೆ. 3m-1 ಒಳಹರಿವುಗಳಿವೆ ಎಂದು ಭಾವಿಸೋಣ (ಇಲ್ಲಿ m ಸಮವಾಗಿರುತ್ತದೆ). ಮೊದಲ 2 ಮೀ ಒಳಹರಿವುಗಳೆಂದರೆಃ 2 ಮೀ-1,2 ಮೀ-1,2 ಮೀ-2,2 ಮೀ-2,., ಮೀ, ಮೀ. ಕೊನೆಯ ಎಂ-1 ಒಳಹರಿವುಗಳೆಲ್ಲವೂ ಮೀ ಆಗಿರುತ್ತವೆ. ನಂತರ ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ ಹಿಂತಿರುಗುತ್ತದೆಃ 2 ಮೀ-1, ಮೀ, ಮೀ 2 ಮೀ-1, ಮೀ, ಮೀ 2 ಮೀ-2, ಮೀ + 1, ಮೀ 2 ಮೀ-2, ಮೀ + 1, ಮೀ. 3 ಮೀ/2,3 ಮೀ/2-1, ಮೀ 3 ಮೀ/2,3 ಮೀ/2-2 ಕನಿಷ್ಠ 3 ಮೀ-1. ಆದರೆ ಸೂಕ್ತವಾದ ವಿಭಾಗವೆಂದರೆಃ 2 ಮೀ-1,2 ಮೀ-2, ಮೀ, ಮೀ 2 ಮೀ-2, ಮೀ, ಮೀ 2 ಮೀ-3, ಮೀ + 1, ಮೀ 2 ಮೀ-3, ಮೀ + 1, ಮೀ. 3 ಮೀ/2,3 ಮೀ/2-2, ಮೀ 3 ಮೀ/2,3 ಮೀ/2-2, ಮೀ 3 ಮೀ/2-2, ಮೀ 3 ಮೀ/2-2,3 ಮೀ/2-2, ಮೀ ಕನಿಷ್ಠ 4 ಮೀ-2. ನಿರ್ಬಂಧಿತ ಎಲ್ಪಿಟಿ ಎಂಬ ಎಲ್ಪಿಟಿಯ ಒಂದು ರೂಪಾಂತರವಿದೆ, ಇದನ್ನು ನಿರ್ಬಂಧಿತ-ಎಲ್ಪಿಟಿ ಅಥವಾ ಆರ್ಎಲ್ಪಿಟಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ, ಇದರಲ್ಲಿ ಇನ್ಪುಟ್ಗಳನ್ನು ಶ್ರೇಣಿಗಳು ಎಂದು ಕರೆಯಲಾಗುವ ಗಾತ್ರದ ಎಂನ ಉಪಗುಂಪುಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗುತ್ತದೆ (ಶ್ರೇಣಿ 1 ಅತಿದೊಡ್ಡ ಎಂ ಇನ್ಪುಟ್ಗಳನ್ನು, ಶ್ರೇಣಿ 2 ಅತಿದೊಡ್ಡ ಎಂ ಇನ್ಪುಟ್ಗಳನ್ನು, ಇತ್ಯಾದಿಗಳನ್ನು ಹೊಂದಿರುತ್ತದೆ). ಪ್ರತಿ ಶ್ರೇಣಿಯಲ್ಲಿನ ಇನ್ಪುಟ್ಗಳನ್ನು ವಿವಿಧ ಬಿನ್ಗಳಿಗೆ ನಿಯೋಜಿಸಬೇಕುಃ ಮೊದಲು 1ನೇ ಶ್ರೇಣಿ, ನಂತರ 2ನೇ ಶ್ರೇಣಿ, ಇತ್ಯಾದಿ. ಆರ್ಎಲ್ಪಿಟಿಯಲ್ಲಿನ ಕನಿಷ್ಠ ಮೊತ್ತವು ಎಲ್ಪಿಟಿಯಲ್ಲಿನ ಕನಿಷ್ಠ ಮೊತ್ತವಾಗಿದೆ. ಕನಿಷ್ಠ ಮೊತ್ತವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಲು ಆರ್ಎಲ್ಪಿಟಿಯ ಅಂದಾಜು ಅನುಪಾತವು ಗರಿಷ್ಠ m ಆಗಿರುತ್ತದೆ. ಸರಾಸರಿ-ಪ್ರಕರಣ ಗರಿಷ್ಠ ಮೊತ್ತ ಸರಾಸರಿ ಸಂದರ್ಭದಲ್ಲಿ, ಇನ್ಪುಟ್ ಸಂಖ್ಯೆಗಳನ್ನು [0,1] ನಲ್ಲಿ ಏಕರೂಪವಾಗಿ ವಿತರಿಸಿದರೆ, ಎಲ್ಪಿಟಿ ವೇಳಾಪಟ್ಟಿಯಲ್ಲಿ ಅತಿದೊಡ್ಡ ಮೊತ್ತವು ಈ ಕೆಳಗಿನ ಗುಣಲಕ್ಷಣಗಳನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆಃ m = 2 ಯಂತ್ರಗಳಿಗೆ ನಿರೀಕ್ಷಿತ ಅತಿದೊಡ್ಡ ಮೊತ್ತವು ಕನಿಷ್ಠ ಮತ್ತು ಗರಿಷ್ಠ, ಇಲ್ಲಿ n ಎಂಬುದು ಇನ್ಪುಟ್ಗಳ ಸಂಖ್ಯೆಯಾಗಿದೆ. ಹೆಚ್ಚಿನ ಸಮಯಗಳಲ್ಲಿ ಅತಿದೊಡ್ಡ ಮೊತ್ತವು ಬಹುತೇಕ ಖಚಿತವಾಗಿ ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ, ಮತ್ತು ನಿರೀಕ್ಷೆಯಲ್ಲಿ, ಇನ್ಪುಟ್ಗಳ ಸಂಖ್ಯೆ ಎಲ್ಲಿದೆ. ಎಲ್ಪಿಟಿ ಅತಿದೊಡ್ಡ ಮೊತ್ತ ಮತ್ತು ಅತ್ಯುತ್ತಮ ಅತಿದೊಡ್ಡ ಮೊತ್ತದ ನಡುವಿನ ವ್ಯತ್ಯಾಸವು ಬಹುತೇಕ ಖಚಿತವಾಗಿ (ಏಕರೂಪದ ಅಥವಾ ಋಣಾತ್ಮಕ ಘಾತೀಯ ವಿತರಣೆಗಳಿಗೆ), ಮತ್ತು ಹೆಚ್ಚಿನ ನಿರೀಕ್ಷೆಯಲ್ಲಿ (ಏಕರೂಪದ ವಿತರಣೆಗಾಗಿ) ಇರುತ್ತದೆ. ಈ ಫಲಿತಾಂಶಗಳು ವಿಭಿನ್ನ ವೇಗಗಳನ್ನು ಹೊಂದಿರುವ ಯಂತ್ರಗಳಿಗೂ ಸಹ ಅನ್ವಯಿಸುತ್ತವೆ. ಸಾಮಾನ್ಯ ಉದ್ದೇಶಗಳು Ci (1 ಮತ್ತು m ನಡುವಿನ i ಗೆ) ಒಂದು ನಿರ್ದಿಷ್ಟ ವಿಭಾಗದಲ್ಲಿರುವ ಉಪಗುಂಪು i ಯ ಮೊತ್ತವಾಗಿರಲಿ. ಆಬ್ಜೆಕ್ಟಿವ್ ಫಂಕ್ಷನ್ ಮ್ಯಾಕ್ಸ್ (ಸಿಐ) ಅನ್ನು ಕಡಿಮೆ ಮಾಡುವ ಬದಲು, ಆಬ್ಜೆಕ್ಟಿವ್ ಫಂಕ್ಷನ್ ಮ್ಯಾಕ್ಸ್ (ಎಫ್ (ಸಿಐ)) ಅನ್ನು ಕಡಿಮೆ ಮಾಡಬಹುದು, ಅಲ್ಲಿ ಎಫ್ ಯಾವುದೇ ಸ್ಥಿರ ಕಾರ್ಯವಾಗಿದೆ. ಅಂತೆಯೇ, ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯದ ಮೊತ್ತವನ್ನು (f (Ci)) ಕಡಿಮೆ ಮಾಡಬಹುದು. ಎಫ್ ಈ ಕೆಳಗಿನ ಎರಡು ಷರತ್ತುಗಳನ್ನು ಪೂರೈಸಿದರೆಃ ಷರತ್ತು ಎಫ್ * ಎಂಬ ಬಲವಾದ ನಿರಂತರತೆಯ ಷರತ್ತುಃ ಪ್ರತಿ ε> 0 ಗೆ δ> 0 ಅಸ್ತಿತ್ವದಲ್ಲಿದೆ, ಅಂದರೆ, |y-x | <δx ಆಗಿದ್ದರೆ, ನಂತರ |f (y)-f (x) | <εf (x). ಕನ್ವೆಕ್ಸಿಟಿ. ನಂತರ ಎಲ್ಪಿಟಿ ನಿಯಮವು ಮೊತ್ತವನ್ನು (ಎಫ್ (ಸಿಐ)) ಕಡಿಮೆ ಮಾಡಲು ಸೀಮಿತ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ. ಇತರ ಸೆಟ್ಟಿಂಗ್ಗಳಿಗೆ ಹೊಂದಾಣಿಕೆಗಳು ಒಂದೇ ರೀತಿಯ ಯಂತ್ರಗಳ ವೇಳಾಪಟ್ಟಿಯ ಸರಳ ಪ್ರಕರಣವನ್ನು ಹೊರತುಪಡಿಸಿ, ಎಲ್ಪಿಟಿಯನ್ನು ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ಸೆಟ್ಟಿಂಗ್ಗಳಿಗೆ ಅಳವಡಿಸಲಾಗಿದೆ. ಏಕರೂಪದ ಯಂತ್ರಗಳು ಏಕರೂಪದ ಯಂತ್ರಗಳ ವೇಳಾಪಟ್ಟಿಯಲ್ಲಿ, ವಿವಿಧ ಯಂತ್ರಗಳು ವಿಭಿನ್ನ ವೇಗಗಳನ್ನು ಹೊಂದಿರಬಹುದು. ಎಲ್ಪಿಟಿ ನಿಯಮವು ಪ್ರತಿಯೊಂದು ಕೆಲಸವನ್ನು ಯಂತ್ರಕ್ಕೆ ನಿಯೋಜಿಸುತ್ತದೆ, ಅದರ ಪೂರ್ಣಗೊಳಿಸುವ ಸಮಯವು ಶೀಘ್ರವಾಗಿರುತ್ತದೆ (ಅಂದರೆ, ಈ ಯಂತ್ರವು ಇತರ ಎಲ್ಲಾ ಯಂತ್ರಗಳಿಗಿಂತ ಮುಂಚಿತವಾಗಿ ಆ ಕೆಲಸವನ್ನು ಮುಗಿಸುವಷ್ಟು ವೇಗದಲ್ಲಿದ್ದರೆ, ಎಲ್ಪಿಟಿ ದೊಡ್ಡ ವಿದ್ಯುತ್ ಹೊರೆ ಹೊಂದಿರುವ ಯಂತ್ರಕ್ಕೆ ಕೆಲಸವನ್ನು ನಿಯೋಜಿಸಬಹುದು). ಗೊನ್ಜಾಲೆಜ್, ಇಬಾರಾ ಮತ್ತು ಸಾಹ್ನಿ ಎಂ ಏಕರೂಪದ ಯಂತ್ರಗಳೊಂದಿಗೆ ಎಲ್ಪಿಟಿಯ ಅಂದಾಜು ಅನುಪಾತವು ಗರಿಷ್ಠವಾಗಿದೆ ಎಂದು ತೋರಿಸುತ್ತದೆ. ಇದು ಬಿಗಿಯಾಗಿಲ್ಲ, ಆದರೆ m ಅನಂತವನ್ನು ಸಮೀಪಿಸಿದಾಗ 1.5 ರ ಲಕ್ಷಣರಹಿತ ಕೆಳ ಮಿತಿಯಿರುತ್ತದೆ. m = 2 ಯಂತ್ರಗಳ ವಿಶೇಷ ಸಂದರ್ಭದಲ್ಲಿ, ಅಂದಾಜು ಅನುಪಾತವು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ ಮತ್ತು ಅದು ಬಿಗಿಯಾಗಿರುತ್ತದೆ. ಮಿರಾಲ್ಟ್, ಓರ್ಲಿನ್ ಮತ್ತು ವೊಹ್ರಾ ಎರಡು ಯಂತ್ರಗಳೊಂದಿಗೆ ಒಂದು ಸೆಟ್ಟಿಂಗ್ ಅನ್ನು ಅಧ್ಯಯನ ಮಾಡುತ್ತಾರೆ, ಇದರಲ್ಲಿ ಒಂದು ಯಂತ್ರವು ಇನ್ನೊಂದಕ್ಕಿಂತ q ಪಟ್ಟು ವೇಗವಾಗಿರುತ್ತದೆ. ಅವರು ಎಲ್ಪಿಟಿಯ ಅಂದಾಜು ಅನುಪಾತವನ್ನು q ನ ಕಾರ್ಯವಾಗಿ ಲೆಕ್ಕ ಹಾಕುತ್ತಾರೆ. q = 1 ಆಗಿದ್ದಾಗ, ಅವುಗಳ ಫಲಿತಾಂಶವು ಒಂದೇ ರೀತಿಯ ಯಂತ್ರಗಳಿಗೆ ಹೆಸರುವಾಸಿಯಾದ 7/6 ಅಂಶದೊಂದಿಗೆ ಹೊಂದಿಕೆಯಾಗುತ್ತದೆ. ಕೌಲಾಮಾಸ್ ಮತ್ತು ಕಿಪರಿಸಿಗಳು ಎಲ್ಪಿಟಿಯ ಮಾರ್ಪಾಡುಗಳನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ, ಇದರಲ್ಲಿ ಮೂರು ದೀರ್ಘಾವಧಿಯ ಉದ್ಯೋಗಗಳನ್ನು ಅತ್ಯುತ್ತಮವಾಗಿ ನಿಗದಿಪಡಿಸಲಾಗಿದೆ ಮತ್ತು ಉಳಿದ ಉದ್ಯೋಗಗಳನ್ನು ಎಲ್ಪಿಟಿ ನಿಯಮದ ಆಧಾರದ ಮೇಲೆ ನಿಗದಿಪಡಿಸಲಾಗಿದೆ. ಎರಡು ಯಂತ್ರಗಳ ಅಂದಾಜು ಅನುಪಾತವು ಮತ್ತು ಅದು ಬಿಗಿಯಾಗಿರುತ್ತದೆ. ಕಾರ್ಡಿನಲಿಟಿ ನಿರ್ಬಂಧಗಳು ಸಮತೋಲಿತ ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯಲ್ಲಿ, ಪ್ರತಿ ಯಂತ್ರಕ್ಕೆ ನಿಯೋಜಿಸಬಹುದಾದ ಉದ್ಯೋಗಗಳ ಸಂಖ್ಯೆಯ ಮೇಲೆ ನಿರ್ಬಂಧಗಳಿವೆ. ಒಂದು ಸರಳ ನಿರ್ಬಂಧವೆಂದರೆ ಪ್ರತಿ ಯಂತ್ರವು ಗರಿಷ್ಠ ಸಿ ಉದ್ಯೋಗಗಳಲ್ಲಿ ಪ್ರಕ್ರಿಯೆಗೊಳಿಸಬಲ್ಲದು. ಎಲ್ಪಿಟಿ ನಿಯಮವು ಸಿಗಿಂತ ಕಡಿಮೆ ಉದ್ಯೋಗಗಳನ್ನು ಹೊಂದಿರುವ ಯಂತ್ರಗಳಲ್ಲಿ ಅತಿ ಕಡಿಮೆ ಭಾರವನ್ನು ಹೊಂದಿರುವ ಯಂತ್ರಕ್ಕೆ ಪ್ರತಿ ಕೆಲಸವನ್ನು ನಿಯೋಜಿಸುತ್ತದೆ. ಈ ನಿಯಮವನ್ನು ಮಾರ್ಪಡಿಸಿದ ಎಲ್ಪಿಟಿ ಅಥವಾ ಎಂಎಲ್ಪಿಟಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಕೆಲ್ಲೆರರ್ ಮತ್ತು ವೂಯಿಂಗರ್ ಅವರು ಗರಿಷ್ಠ 3 * ಮೀ ಉದ್ಯೋಗಗಳಿರುವ ರೂಪಾಂತರವನ್ನು ಅಧ್ಯಯನ ಮಾಡುತ್ತಾರೆ ಮತ್ತು ಪ್ರತಿ ಯಂತ್ರವು ಗರಿಷ್ಠ 3 ಉದ್ಯೋಗಗಳನ್ನು ಹೊಂದಿರಬೇಕು (ಇದನ್ನು 3-ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯ ಸಾಮಾನ್ಯೀಕರಣವಾಗಿ ನೋಡಬಹುದು). ಎಂ. ಎಲ್. ಪಿ. ಟಿ ಕನಿಷ್ಠ ಅತಿದೊಡ್ಡ ಮೊತ್ತವನ್ನು ಸಾಧಿಸುತ್ತದೆ ಎಂದು ಅವು ತೋರಿಸುತ್ತವೆ, ಇದು ಅನಿಯಂತ್ರಿತ ಸಮಸ್ಯೆಗೆ ಎಲ್ಪಿಟಿ ಸಾಧಿಸುವ ಅದೇ ಅಂದಾಜು ಅನುಪಾತವಾಗಿದೆ. ಎಂ. ಎಲ್. ಪಿ. ಟಿ. ಗೆ ಮಿತಿಯು ಬಿಗಿಯಾಗಿರುತ್ತದೆ. ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ಕಾರ್ಡಿನಲಿಟಿ ನಿರ್ಬಂಧಗಳಿಗೆ (ಸಿ> 3) ಎಂ. ಎಲ್. ಪಿ. ಟಿ ಒಂದೇ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಊಹಿಸಲಾಗಿದೆ. ಪ್ರಸ್ತುತ, ಸಾಮಾನ್ಯ ಸಿ> 3 ಗೆ ಎಂ. ಎಲ್. ಪಿ. ಟಿ ಯ ಅಂದಾಜು ಅನುಪಾತವು ಗರಿಷ್ಠ 2 ಎಂದು ತಿಳಿದಿದೆ. ಚೆನ್, ಹಿ ಮತ್ತು ಲಿನ್, ಅದೇ ಸಮಸ್ಯೆಗೆ, ಎಂ. ಎಲ್. ಪಿ. ಟಿ ಕನಿಷ್ಠ ಗರಿಷ್ಠ ಚಿಕ್ಕ ಮೊತ್ತವನ್ನು ಸಾಧಿಸುತ್ತದೆ ಎಂದು ತೋರಿಸುತ್ತಾರೆ, ಇದು ಮತ್ತೆ ಅನಿಯಂತ್ರಿತ ಸಮಸ್ಯೆಗೆ ಎಲ್ಪಿಟಿ ಸಾಧಿಸುವ ಅದೇ ಅನುಪಾತವಾಗಿದೆ. ಮತ್ತೊಂದು ಅಡಚಣೆಯೆಂದರೆ, ಎಲ್ಲಾ ಯಂತ್ರಗಳಲ್ಲಿನ ಕೆಲಸಗಳ ಸಂಖ್ಯೆಯನ್ನು ಮೇಲಕ್ಕೆ ಅಥವಾ ಕೆಳಕ್ಕೆ ಪೂರ್ಣಗೊಳಿಸಬೇಕು. ನಿರ್ಬಂಧಿತ ಎಲ್ಪಿಟಿ ಅಥವಾ ಆರ್ಎಲ್ಪಿಟಿ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಎಲ್ಪಿಟಿಯ ರೂಪಾಂತರದಲ್ಲಿ, ಒಳಹರಿವುಗಳನ್ನು ಜೋಡಿಯಾಗಿ ನಿಗದಿಪಡಿಸಲಾಗುತ್ತದೆ-ಪ್ರತಿ ಯಂತ್ರಕ್ಕೆ ಒಂದು (ಮೀ = 2 ಯಂತ್ರಗಳಿಗೆ). ಪರಿಣಾಮವಾಗಿ ವಿಭಜನೆಯು ವಿನ್ಯಾಸದಿಂದ ಸಮತೋಲನಗೊಳ್ಳುತ್ತದೆ. ಇನ್ಪುಟ್ಗಳು ಏಕರೂಪವಾಗಿ ವಿತರಿಸಲ್ಪಟ್ಟ ಯಾದೃಚ್ಛಿಕ ಅಸ್ಥಿರಗಳಾಗಿದ್ದಾಗ ಆರ್ಎಲ್ಪಿಟಿಯ ನಿರೀಕ್ಷಿತ ಅತಿದೊಡ್ಡ ಮೊತ್ತವು ನಿಖರವಾಗಿದೆ ಎಂದು ಕಾಫ್ಮನ್, ಫ್ರೆಡೆರಿಕ್ಸನ್ ಮತ್ತು ಲ್ಯೂಕರ್ ತೋರಿಸುತ್ತಾರೆ. ಅತಿದೊಡ್ಡ ಮತ್ತು ಚಿಕ್ಕ ಮೊತ್ತದ ನಡುವಿನ ನಿರೀಕ್ಷಿತ ವ್ಯತ್ಯಾಸವೆಂದರೆ. ಕರ್ನಲ್ ನಿರ್ಬಂಧಗಳು-ಏಕಕಾಲಿಕ ಲಭ್ಯತೆ ಕರ್ನಲ್ ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯಲ್ಲಿ, ಕರ್ನಲ್ಗಳು ಎಂದು ಕರೆಯಲ್ಪಡುವ ಕೆಲವು ಪೂರ್ವ-ನಿರ್ದಿಷ್ಟ ಉದ್ಯೋಗಗಳಿವೆ, ಮತ್ತು ಪ್ರತಿ ಕರ್ನಲ್ ಅನ್ನು ವಿಶಿಷ್ಟ ಯಂತ್ರಕ್ಕೆ ನಿಗದಿಪಡಿಸಬೇಕು. ಯಂತ್ರಗಳು ವಿವಿಧ ಸಮಯಗಳಲ್ಲಿ ಲಭ್ಯವಿರುವಾಗ ವೇಳಾಪಟ್ಟಿಯನ್ನು ನಿಗದಿಪಡಿಸುವುದು ಸಮಾನವಾದ ಸಮಸ್ಯೆಯಾಗಿದೆಃ ಪ್ರತಿ ಯಂತ್ರವು ಕೆಲವು ಸಮಯಗಳಲ್ಲಿ ಲಭ್ಯವಾಗುತ್ತದೆ (ಸಮಯವನ್ನು ಕರ್ನಲ್ ಕೆಲಸದ ಉದ್ದವೆಂದು ಪರಿಗಣಿಸಬಹುದು). ಎಸ್ಎಲ್ಪಿಟಿ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಒಂದು ಸರಳ ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಲ್ಗಾರಿದಮ್, ಪ್ರತಿ ಕರ್ನಲ್ ಅನ್ನು ಬೇರೆ ಉಪವಿಭಾಗಕ್ಕೆ ನಿಯೋಜಿಸುತ್ತದೆ ಮತ್ತು ನಂತರ ಎಲ್ಪಿಟಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನಡೆಸುತ್ತದೆ. ಈ ಶೋಧಕವು ಕನಿಷ್ಠ ಅತಿದೊಡ್ಡ ಮೊತ್ತಕ್ಕೆ ಬಿಗಿಯಾದ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಲೀ ಸಾಬೀತುಪಡಿಸಿದ್ದಾರೆ. ನಂತರ ಅವರು ಎರಡನೇ ಹಂತದಲ್ಲಿ, ಎಲ್ಪಿಟಿಯ ಮಾರ್ಪಡಿಸಿದ ಆವೃತ್ತಿಯನ್ನು ಓಡಲು ಸೂಚಿಸುತ್ತಾರೆ ಮತ್ತು ಅದು ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಸಾಧಿಸುತ್ತದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸುತ್ತಾರೆ. ಲಿನ್, ಯಾವೊ ಮತ್ತು ಅವರು ಈ ಶೋಧಕವು ಗರಿಷ್ಠ ಚಿಕ್ಕ ಮೊತ್ತಕ್ಕೆ ಬಿಗಿಯಾದ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸುತ್ತಾರೆ. ಶೆನ್, ವಾಂಗ್ ಮತ್ತು ವಾಂಗ್ ಈ ಸೆಟ್ಟಿಂಗ್ಗಾಗಿ ವಿಭಿನ್ನ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯಗಳನ್ನು ಅಧ್ಯಯನ ಮಾಡುತ್ತಾರೆ ಮತ್ತು ಬಹುಪದ-ಸಮಯದ ಕ್ರಮಾವಳಿಗಳನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ಆನ್ಲೈನ್ ಸೆಟ್ಟಿಂಗ್ಗಳು ಸಾಮಾನ್ಯವಾಗಿ, ಇನ್ಪುಟ್ಗಳು ಆನ್ಲೈನ್ನಲ್ಲಿ ಬರುತ್ತವೆ ಮತ್ತು ಅವು ಬಂದಾಗ ಮಾತ್ರ ಅವುಗಳ ಗಾತ್ರಗಳು ತಿಳಿಯುತ್ತವೆ. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಅವುಗಳನ್ನು ಮುಂಚಿತವಾಗಿ ವಿಂಗಡಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ. ಪಟ್ಟಿ ವೇಳಾಪಟ್ಟಿ ಇದೇ ರೀತಿಯ ಅಲ್ಗಾರಿದಮ್ ಆಗಿದ್ದು ಅದು ಯಾವುದೇ ಕ್ರಮದಲ್ಲಿ ಪಟ್ಟಿಯನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ, ಅಗತ್ಯವಾಗಿ ವಿಂಗಡಿಸಲಾಗಿಲ್ಲ. ಇದರ ಅಂದಾಜು ಅನುಪಾತವು. ಆನ್ಲೈನ್ ಸೆಟ್ಟಿಂಗ್ಗೆ ಎಲ್ಪಿಟಿಯ ಹೆಚ್ಚು ಅತ್ಯಾಧುನಿಕ ರೂಪಾಂತರವು 3/2 ರ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಸಾಧಿಸುತ್ತದೆ. ಅನುಷ್ಠಾನಗಳು ಪೈಥಾನ್ಃ ಎಲ್ಪಿಟಿ ("ದುರಾಸೆ") ಯ ಅನುಷ್ಠಾನವು ಸಂಖ್ಯೆ ವಿಭಜನೆ ಪ್ಯಾಕೇಜಿನಲ್ಲಿ ಮತ್ತು ಪ್ರಿಟಿಪಿ ಪ್ಯಾಕೇಜ್ನಲ್ಲಿಯೂ ಇದೆ. ಗ್ರೀಡಿ ಸಂಖ್ಯೆ ವಿಭಜನೆಯನ್ನು ಸಹ ನೋಡಿ-ಬಹುಪಥ ಸಂಖ್ಯೆ ವಿಭಜನೆಯ ಸಮಸ್ಯೆಗಾಗಿ ಎಲ್ಪಿಟಿಯ ಸಾಮಾನ್ಯೀಕರಣಗಳು ಮತ್ತು ವಿಸ್ತರಣೆಗಳು. ಟಿಪ್ಪಣಿಗಳು ಉಲ್ಲೇಖಗಳ ವೇಳಾಪಟ್ಟಿ ಕ್ರಮಾವಳಿಗಳು ಸಂಖ್ಯೆ ವಿಭಜನೆ