Balanced number partitioning
ಸಮತೋಲಿತ ಸಂಖ್ಯೆ ವಿಭಜನೆಯು ಬಹುಮಾರ್ಗ ಸಂಖ್ಯೆ ವಿಭಜನೆಯ ಒಂದು ರೂಪಾಂತರವಾಗಿದೆ, ಇದರಲ್ಲಿ ಪ್ರತಿ ಗುಂಪಿಗೆ ನಿಗದಿಪಡಿಸಿದ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯ ಮೇಲೆ ನಿರ್ಬಂಧಗಳಿವೆ. ಸಮಸ್ಯೆಯ ಇನ್ಪುಟ್ ವಿವಿಧ ಗಾತ್ರಗಳ n ಐಟಂಗಳ ಒಂದು ಸೆಟ್, ಮತ್ತು ಎರಡು ಪೂರ್ಣಾಂಕಗಳು m, k. ಔಟ್ಪುಟ್ ಎಂದರೆ ಐಟಂಗಳನ್ನು m ಉಪಗುಂಪುಗಳಾಗಿ ವಿಭಜಿಸುವುದು, ಅಂದರೆ ಪ್ರತಿ ಉಪಗುಂಪುಗಳಲ್ಲಿನ ಐಟಂಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ k ಆಗಿರುತ್ತದೆ. ಇದಕ್ಕೆ ಒಳಪಟ್ಟು, m ಉಪಗುಂಪುಗಳಲ್ಲಿನ ಗಾತ್ರಗಳ ಮೊತ್ತವು ಸಾಧ್ಯವಾದಷ್ಟು ಒಂದೇ ಆಗಿರಬೇಕು. ಒಂದು ಉದಾಹರಣೆಯೆಂದರೆ ಒಂದೇ ರೀತಿಯ ಯಂತ್ರಗಳ ವೇಳಾಪಟ್ಟಿ, ಅಲ್ಲಿ ಪ್ರತಿ ಯಂತ್ರವು ಹೆಚ್ಚಿನ k ಉದ್ಯೋಗಗಳನ್ನು ಹಿಡಿದಿಟ್ಟುಕೊಳ್ಳುವ ಜಾಬ್-ಕ್ಯೂ ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ. ವಿಎಲ್ಎಸ್ಐ ಚಿಪ್ಗಳ ತಯಾರಿಕೆಯಲ್ಲಿ ಮತ್ತು ಹೊಂದಿಕೊಳ್ಳುವ ಉತ್ಪಾದನಾ ವ್ಯವಸ್ಥೆಗಳಲ್ಲಿ ಯಂತ್ರಗಳಿಗೆ ಉಪಕರಣಗಳನ್ನು ನಿಯೋಜಿಸುವಲ್ಲಿ ಈ ಸಮಸ್ಯೆಯು ಅನ್ವಯಗಳನ್ನು ಹೊಂದಿದೆ. ಅತ್ಯುತ್ತಮ ಉದ್ಯೋಗ ವೇಳಾಪಟ್ಟಿ ಸಮಸ್ಯೆಗಳಿಗೆ ಪ್ರಮಾಣಿತ ಮೂರು-ಕ್ಷೇತ್ರ ಸಂಕೇತದಲ್ಲಿ, ಅತಿದೊಡ್ಡ ಮೊತ್ತವನ್ನು ಕಡಿಮೆ ಮಾಡುವ ಸಮಸ್ಯೆಯನ್ನು ಕೆಲವೊಮ್ಮೆ "P | #≤ k | Cmax" ಎಂದು ಸೂಚಿಸಲಾಗುತ್ತದೆ. ಮಧ್ಯದ ಕ್ಷೇತ್ರ "#≤ k" ಪ್ರತಿ ಯಂತ್ರದಲ್ಲಿನ ಉದ್ಯೋಗಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ k ಆಗಿರಬೇಕು ಎಂದು ಸೂಚಿಸುತ್ತದೆ. ಇದು "" ಎಂದು ಸೂಚಿಸಲಾಗುವ ನಿರ್ಬಂಧಿತವಲ್ಲದ ಆವೃತ್ತಿಗೆ ವ್ಯತಿರಿಕ್ತವಾಗಿದೆ. ದ್ವಿಮುಖ ಸಮತೋಲಿತ ವಿಭಜನೆಯು ಎರಡು ಉಪಗುಂಪುಗಳು (m = 2) ಇರಬೇಕಾದಾಗ ದ್ವಿಮುಖ ಸಮತೋಲಿತ ವಿಭಜನೆ ಎಂದು ಕರೆಯಲಾಗುವ ಒಂದು ಸಾಮಾನ್ಯ ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದೆ. ಎರಡು ಉಪಗುಂಪುಗಳು ನೆಲ (ಎನ್/2) ಮತ್ತು ಸೀಲಿಂಗ್ (ಎನ್/2) ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರಬೇಕು. ಇದು ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯ ಒಂದು ರೂಪಾಂತರವಾಗಿದೆ. ಎರಡು ಉಪಗುಂಪುಗಳಲ್ಲಿನ ಮೊತ್ತಗಳು ಸಮಾನವಾಗಿರುವ ವಿಭಾಗವಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದೆ; ಸಮಸ್ಯೆ [ಎಸ್. ಪಿ. 12] ನೋಡಿ. ಸಮತೋಲಿತ ವಿಭಾಗವನ್ನು ಕಂಡುಹಿಡಿಯುವ ಗುರಿಯನ್ನು ಹೊಂದಿರುವ ಅನೇಕ ಕ್ರಮಾವಳಿಗಳಿವೆ, ಇದರಲ್ಲಿ ಮೊತ್ತವು ಸಾಧ್ಯವಾದಷ್ಟು ಸಮಾನವಾಗಿರುತ್ತದೆ. ಕಾಫ್ಮನ್, ಫ್ರೆಡೆರಿಕ್ಸನ್ ಮತ್ತು ಲ್ಯೂಕರ್ ಅವರು ಎಲ್ಪಿಟಿ ಅಲ್ಗಾರಿದಮ್ನ (ಆರ್ಎಲ್ಪಿಟಿ ಎಂದು ಕರೆಯಲ್ಪಡುವ) ನಿರ್ಬಂಧಿತ ಆವೃತ್ತಿಯನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ, ಇದರಲ್ಲಿ ಇನ್ಪುಟ್ಗಳನ್ನು ಜೋಡಿಯಾಗಿ ನಿಗದಿಪಡಿಸಲಾಗುತ್ತದೆ. ಇನ್ಪುಟ್ಗಳನ್ನು ಏಕರೂಪವಾಗಿ ವಿತರಿಸಿದಾಗ, ಆರ್ಎಲ್ಪಿಟಿಯ ನಿರೀಕ್ಷಿತ ಅತಿದೊಡ್ಡ ಮೊತ್ತವು ನಿಖರವಾಗಿರುತ್ತದೆ. ನಿರೀಕ್ಷಿತ ಕೆಲಸ-ವ್ಯತ್ಯಾಸ (ದೊಡ್ಡ ಮತ್ತು ಚಿಕ್ಕ ಮೊತ್ತದ ನಡುವಿನ ವ್ಯತ್ಯಾಸ). ಲ್ಯೂಕರ್ ಅವರು ಎಲ್ಡಿಎಂ ಅಲ್ಗಾರಿದಮ್ನ ಒಂದು ರೂಪಾಂತರವನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ (ಇದನ್ನು ಜೋಡಿಯಾಗಿ ವಿಭಿನ್ನ ವಿಧಾನ (ಪಿಡಿಎಂ) ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ). ಅದರ ನಿರೀಕ್ಷಿತ ಕೆಲಸ-ವ್ಯತ್ಯಾಸ. ತ್ಸೈ ನಿರ್ಬಂಧಿತ ಅತಿದೊಡ್ಡ ವ್ಯತ್ಯಾಸ (ಆರ್ಎಲ್ಡಿ) ಎಂಬ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ಅದರ ಕೆಲಸ-ವ್ಯತ್ಯಾಸ ಬಹುತೇಕ ಖಚಿತವಾಗಿದೆ. ಯಾಕಿರ್ ಬಿ. ಎಲ್. ಡಿ. ಎಂ. ಎಂದು ಕರೆಯಲ್ಪಡುವ ಎಂ = 2 ಗಾಗಿ ಎಲ್ಡಿಎಂ ಅಲ್ಗಾರಿದಮ್ನ ಸಮತೋಲಿತ ರೂಪಾಂತರವನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾನೆ. ಅದರ ನಿರೀಕ್ಷಿತ ಕೆಲಸ-ವ್ಯತ್ಯಾಸ. ಸಮತೋಲಿತ ದ್ವಿಮುಖ ವಿಭಜನೆಗಾಗಿ ಮೆರ್ಟೆನ್ಸ್ ಯಾವುದೇ ಸಮಯದಲ್ಲಿ ಸಂಪೂರ್ಣ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಒದಗಿಸುತ್ತದೆ. ಇದು ಬಿ. ಎಲ್. ಡಿ. ಎಂ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಸಂಪೂರ್ಣ-ಕರ್ಮಾರ್ಕರ್-ಕಾರ್ಪ್ ಅಲ್ಗಾರಿದಮ್ನೊಂದಿಗೆ ಸಂಯೋಜಿಸುತ್ತದೆ. ಸಮತೋಲಿತ ತ್ರಿವಳಿ ವಿಭಜನೆ 3-ವಿಭಜನೆ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಮತ್ತೊಂದು ವಿಶೇಷ ಪ್ರಕರಣವೆಂದರೆ ಪ್ರತಿ ಉಪವಿಭಾಗದಲ್ಲಿನ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ 3 (k = 3) ಆಗಿರಬೇಕು. ಸಮಾನ ಮೊತ್ತಗಳೊಂದಿಗೆ ಅಂತಹ ವಿಭಾಗವಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವುದು ನಿಖರವಾಗಿ 3-ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯಾಗಿದೆ, ಇದು ಬಲವಾಗಿ ಎನ್ಪಿ-ಹಾರ್ಡ್ ಎಂದು ತಿಳಿದುಬಂದಿದೆ. ಮೊತ್ತವು ಸಾಧ್ಯವಾದಷ್ಟು ಸಮಾನವಾಗಿರುವ ವಿಭಾಗವನ್ನು ಕಂಡುಹಿಡಿಯುವ ಗುರಿಯನ್ನು ಹೊಂದಿರುವ ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳಿವೆ. ಕೆಲ್ಲೆರರ್ ಮತ್ತು ವೂಯಿಂಗರ್ ಎಲ್ಪಿಟಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ತ್ರಿವಳಿ ವಿಭಜನೆಗೆ ಅಳವಡಿಸಿಕೊಳ್ಳುತ್ತಾರೆ (ಅಲ್ಲಿ ಗರಿಷ್ಠ 3 * ಮೀ ಐಟಂಗಳು ಇರುತ್ತವೆ, ಮತ್ತು ಪ್ರತಿ ಉಪವಿಭಾಗವು ಗರಿಷ್ಠ 3 ಐಟಂಗಳನ್ನು ಹೊಂದಿರಬೇಕು). ಅವರ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಮಾರ್ಪಡಿಸಿದ-ಎಲ್ಪಿಟಿ ಅಥವಾ ಎಂಎಲ್ಪಿಟಿ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಇದು ದೊಡ್ಡದಾದ ವಸ್ತುಗಳಿಂದ ಸಣ್ಣದಕ್ಕೆ ವಸ್ತುಗಳನ್ನು ಆರ್ಡರ್ ಮಾಡುತ್ತದೆ ಮತ್ತು ಪ್ರತಿ ವಸ್ತುವನ್ನು 3 ಕ್ಕಿಂತ ಕಡಿಮೆ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರುವ ಡಬ್ಬಿಗಳಲ್ಲಿ ಚಿಕ್ಕ ಮೊತ್ತದೊಂದಿಗೆ ಡಬ್ಬಿಯಲ್ಲಿ ಇರಿಸುತ್ತದೆ. ಎಂಎಲ್ಪಿಟಿ ಅಲ್ಗಾರಿದಮ್ ಕನಿಷ್ಠ ಅತಿದೊಡ್ಡ ಮೊತ್ತವನ್ನು ಸಾಧಿಸುತ್ತದೆ ಎಂದು ಅವರು ತೋರಿಸುತ್ತಾರೆ, ಇದು ಅನಿಯಂತ್ರಿತ ಸಮಸ್ಯೆಗೆ ಎಲ್ಪಿಟಿ ಸಾಧಿಸುವ ಅದೇ ಅಂದಾಜು ಅನುಪಾತವಾಗಿದೆ. ಎಂ. ಎಲ್. ಪಿ. ಟಿ. ಗೆ ಮಿತಿಯು ಬಿಗಿಯಾಗಿರುತ್ತದೆ. ಚೆನ್, ಹಿ ಮತ್ತು ಲಿನ್, ಅದೇ ಸಮಸ್ಯೆಗೆ, ಎಂ. ಎಲ್. ಪಿ. ಟಿ ಕನಿಷ್ಠ ಗರಿಷ್ಠ ಚಿಕ್ಕ ಮೊತ್ತವನ್ನು ಸಾಧಿಸುತ್ತದೆ ಎಂದು ತೋರಿಸುತ್ತಾರೆ, ಇದು ಮತ್ತೆ ಅನಿಯಂತ್ರಿತ ಸಮಸ್ಯೆಗೆ ಎಲ್ಪಿಟಿ ಸಾಧಿಸುವ ಅದೇ ಅನುಪಾತವಾಗಿದೆ. ಕೆಲ್ಲೆರರ್ ಮತ್ತು ಕೊಟೋವ್ ವಿಭಿನ್ನ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ (ನಿಖರವಾಗಿ 3 * ಮೀ ವಸ್ತುಗಳ ಸಂದರ್ಭದಲ್ಲಿ), ಇದು ಕನಿಷ್ಠ ಅತಿದೊಡ್ಡ ಮೊತ್ತವನ್ನು ಸಾಧಿಸುತ್ತದೆ. ದೊಡ್ಡ ಕಾರ್ಡಿನಲಿಟಿಗಳೊಂದಿಗೆ ಸಮತೋಲಿತ ವಿಭಜನೆ ಕೆ-ವಿಭಜನೆ ಎಂದು ಕರೆಯಲ್ಪಡುವ ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ಪ್ರಕರಣವೆಂದರೆ, ಪ್ರತಿ ಉಪವಿಭಾಗದಲ್ಲಿನ ಐಟಂಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ ಕೆ ಆಗಿರಬೇಕು, ಅಲ್ಲಿ ಕೆ ಯಾವುದೇ ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕವಾಗಿರಬಹುದು. ಬಾಬೆಲ್, ಕೆಲ್ಲೆರರ್ ಮತ್ತು ಕೊಟೋವ್ ಕೆ × ಎಂ ಐಟಂಗಳನ್ನು ಹೊಂದಿರುವ ರೂಪಾಂತರವನ್ನು ಅಧ್ಯಯನ ಮಾಡುತ್ತಾರೆ (ಕೆಲವು ಪೂರ್ಣಾಂಕ ಕೆಗೆ), ಮತ್ತು ಪ್ರತಿ ಎಂ ಸೆಟ್ಗಳು ನಿಖರವಾಗಿ ಕೆ ಐಟಂಗಳನ್ನು ಹೊಂದಿರಬೇಕು. ಕನಿಷ್ಠ ಅತಿದೊಡ್ಡ ಮೊತ್ತವನ್ನು ಅಂದಾಜು ಮಾಡಲು ಅವರು ಹಲವಾರು ಹ್ಯೂರಿಸ್ಟಿಕ್ ಅಲ್ಗಾರಿದಮ್ಗಳನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆಃ ಫೋಲ್ಡಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ಃ m = 2 ಗೆ ಸೂಕ್ತವಾಗಿದೆ, ಮತ್ತು ಸಾಮಾನ್ಯವಾಗಿ ಬಿಗಿಯಾದ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ. ವಿನಿಮಯ ಕ್ರಮಾವಳಿಃ ಬಿಗಿಯಾದ ಅಂದಾಜು ಅನುಪಾತ. ಇದು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ನಡೆಯುತ್ತದೆಯೇ ಎಂಬುದು ತಿಳಿದಿಲ್ಲ. ಪ್ರೈಮಲ್-ಡ್ಯುಯಲ್ ಅಲ್ಗಾರಿದಮ್ (ಎಲ್ಪಿಟಿ ಮತ್ತು ಮಲ್ಟಿಫಿಟ್ನ ಸಂಯೋಜನೆ): ಗರಿಷ್ಠ ಅಂದಾಜು ಅನುಪಾತ. m ಸಾಕಷ್ಟು ದೊಡ್ಡದಾಗಿದ್ದಾಗ ಇದು k = 4 ಗೆ ಬಿಗಿಯಾಗಿರುತ್ತದೆ; ನಿಖರವಾದ ಕೆಳ ಮಿತಿಯು). ಮಾರ್ಪಡಿಸಿದ-ಎಲ್ಪಿಟಿ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ ಎಂಬ ಊಹೆಯೂ ಇದೆ. ಪ್ರಸ್ತುತ, ಈ ಊಹೆಯು k = 3ಕ್ಕೆ ಮಾತ್ರ ನಿಜವೆಂದು ತಿಳಿದುಬಂದಿದೆ. ಕೆ> 3 ಗೆ, ಅದರ ಅಂದಾಜು ಅನುಪಾತವು ಗರಿಷ್ಠ 2 ಎಂದು ತಿಳಿದಿದೆ. ಮೈಖೇಲ್ಸ್, ಕಾರ್ಸ್ಟ್, ಆರ್ಟ್ಸ್, ವ್ಯಾನ್ ಲೀವೆನ್ ಮತ್ತು ಸ್ಪಿಕ್ಸ್ಮಾ ಅವರು ಪ್ರತಿ ಎಂ ಸೆಟ್ಗಳು ಸೀಲಿಂಗ್ (ಎನ್/ಮೀ) ಅಥವಾ ಫ್ಲೋರ್ (ಎನ್/ಮೀ) ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರಬೇಕಾದ ರೂಪಾಂತರವನ್ನು ಅಧ್ಯಯನ ಮಾಡುತ್ತಾರೆ (ಆದ್ದರಿಂದ ಕೆ = ಸೀಲಿಂಗ್ (ಎನ್/ಮೀ)). ಅವು ಸಮತೋಲಿತ-ಎಲ್. ಡಿ. ಎಂ. (ಬಿ. ಎಲ್. ಡಿ. ಎಂ.) ಅನ್ನು m = 2 ರಿಂದ ಸಾಮಾನ್ಯ m ಗೆ ವಿಸ್ತರಿಸುತ್ತವೆ. ಸಾಮಾನ್ಯೀಕೃತ ಕ್ರಮಾವಳಿ ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ. ಕನಿಷ್ಠ ಅತಿದೊಡ್ಡ ಮೊತ್ತಕ್ಕೆ ಅದರ ಅಂದಾಜು ಅನುಪಾತವು k = 3ಕ್ಕೆ ನಿಖರವಾಗಿ 4/3, k = 4ಕ್ಕೆ 19/12, k = 5ಕ್ಕೆ 103/60, k = 6ಕ್ಕೆ 643/360 ಮತ್ತು k = 7ಕ್ಕೆ 4603/2520 ಎಂದು ಅವು ಸಾಬೀತುಪಡಿಸುತ್ತವೆ. ಮಿಶ್ರ ಪೂರ್ಣಾಂಕ ರೇಖೀಯ ಕ್ರಮಾವಳಿಯನ್ನು ಪರಿಹರಿಸುವ ಮೂಲಕ ಅನುಪಾತಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲಾಯಿತು. ಸಾಮಾನ್ಯವಾಗಿ (ಯಾವುದೇ k ಗೆ), ಅಂದಾಜು ಅನುಪಾತವು ಕನಿಷ್ಠ ಮತ್ತು ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ. 3,4,5,6,7ರ ನಿಖರವಾದ MILP ಫಲಿತಾಂಶಗಳು ಕೆಳಗಿನ ಮಿತಿಯನ್ನು ಹೊಂದಿರುತ್ತವೆ. ಕೆ> 7 ಗೆ, ಯಾವುದೇ ನಿಖರವಾದ ಫಲಿತಾಂಶಗಳು ತಿಳಿದಿಲ್ಲ, ಆದರೆ ಕೆಳ ಮತ್ತು ಮೇಲಿನ ಮಿತಿಯ ನಡುವಿನ ವ್ಯತ್ಯಾಸವು 0.3% ಕ್ಕಿಂತ ಕಡಿಮೆಯಾಗಿದೆ. ನಿಯತಾಂಕವು ಉಪಗುಂಪುಗಳ (m) ಸಂಖ್ಯೆಯಾದಾಗ, ಅಂದಾಜು ಅನುಪಾತವು ನಿಖರವಾಗಿರುತ್ತದೆ. ಇನ್ಪುಟ್ಗಳನ್ನು ಏಕರೂಪವಾಗಿ ವಿತರಿಸಿದಾಗ ಮತ್ತು ಅವುಗಳ ವಿತರಣೆಯನ್ನು ವಕ್ರಗೊಳಿಸಿದಾಗ ಎರಡೂ ಬಿ. ಎಲ್. ಡಿ. ಎಂ ಹೆಚ್ಚಿನ ಕೆಲಸ-ವ್ಯತ್ಯಾಸದೊಂದಿಗೆ (ಹೆಚ್ಚಿನ ಮತ್ತು ಕಡಿಮೆ ಮೊತ್ತದ ನಡುವಿನ ವ್ಯತ್ಯಾಸ) ವಿಭಾಗಗಳನ್ನು ನೀಡಬಹುದು ಎಂದು ಜಾಂಗ್, ಮೌರಟಿಡಿಸ್ ಮತ್ತು ಪಾಂಗ್ ತೋರಿಸುತ್ತಾರೆ. ಅವರು ಎರಡು ಪರ್ಯಾಯ ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ಗಳನ್ನು ಪ್ರಸ್ತಾಪಿಸುತ್ತಾರೆಃ ವಿತರಣೆಯು ಏಕರೂಪವಾಗಿದ್ದಾಗ ಬಿ. ಎಲ್. ಡಿ. ಎಂ. ನ ಕೆಲಸ-ವ್ಯತ್ಯಾಸವನ್ನು ಎಲ್. ಆರ್. ಎಂ. ಮೂರನೇ ಒಂದು ಭಾಗಕ್ಕೆ ಕಡಿಮೆ ಮಾಡುತ್ತದೆ; ವಿತರಣೆಯನ್ನು ವಕ್ರಗೊಳಿಸಿದಾಗ ಮೆಲ್ಡ್ ಕೆಲಸ-ವ್ಯತ್ಯಾಸವನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತದೆ. ಹೈಬ್ರಿಡ್ ಅಲ್ಗಾರಿದಮ್ BLDM, LRM ಮತ್ತು Meld ಅನ್ನು ಸಂಯೋಜಿಸುತ್ತದೆ ಮತ್ತು ವಿಭಿನ್ನ ದತ್ತಾಂಶ ವಿತರಣೆಗಳಿಗೆ ಕ್ರಿಯಾತ್ಮಕವಾಗಿ ಹೊಂದಿಕೊಳ್ಳುತ್ತದೆ. ಕೆ ಅನ್ನು ಸ್ಥಿರಗೊಳಿಸಿದಾಗ, ಸಮತೋಲಿತ ವಿಭಜನೆಗಾಗಿ ಹೋಚ್ಬಾಮ್ ಮತ್ತು ಸ್ಮಾಯ್ಸ್ನ ಪಿಟಿಎಎಸ್ ಅನ್ನು ಬಳಸಬಹುದು. ಕೆ ಇನ್ಪುಟ್ನ ಭಾಗವಾಗಿದ್ದಾಗ, ಪ್ರಸ್ತುತ ಯಾವುದೇ ಪಿಟಿಎಎಸ್ ತಿಳಿದಿಲ್ಲ. ಡೆಲ್ 'ಅಮಿಕೋ ಮತ್ತು ಮಾರ್ಟೆಲ್ಲೊ ಎಲ್ಲಾ ಸೆಟ್ಗಳಲ್ಲಿನ ವಸ್ತುಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠ ಕೆ ಆಗಿದ್ದಾಗ ಅತಿದೊಡ್ಡ ಮೊತ್ತವನ್ನು ಕಡಿಮೆ ಮಾಡುವ ಸಮಸ್ಯೆಯನ್ನು ಅಧ್ಯಯನ ಮಾಡುತ್ತಾರೆ. ಈ ರೂಪಾಂತರದ ರೇಖೀಯ-ಪ್ರೋಗ್ರಾಂ ಸಡಿಲಿಕೆಯು ಅನಿಯಂತ್ರಿತ ರೂಪಾಂತರದ ಎಲ್ಪಿ ಸಡಿಲಿಕೆಯಂತೆಯೇ ಅತ್ಯುತ್ತಮ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಅವರು ತೋರಿಸುತ್ತಾರೆ. xi ಎಂಬ ಅಭಿವ್ಯಕ್ತಿಯು, ದೊಡ್ಡದರಿಂದ ಚಿಕ್ಕದಕ್ಕೆ ಆದೇಶಿಸಲಾದ ಒಳಹರಿವು, ಸೂಕ್ತವಾದ ದೊಡ್ಡ-ಮೊತ್ತಕ್ಕೆ ಕಡಿಮೆ ಮಿತಿಯಾಗಿದೆ, ಮತ್ತು ಅದರ ಕೆಟ್ಟ-ಪ್ರಕರಣ ಅನುಪಾತವು ಎರಡೂ ರೂಪಾಂತರಗಳಲ್ಲಿ 1/2 ಆಗಿದೆ. ಸುಧಾರಿತ ಅಭಿವ್ಯಕ್ತಿಯು ಅನಿಯಂತ್ರಿತ ರೂಪಾಂತರದಲ್ಲಿ 2/3 ಮತ್ತು ನಿರ್ಬಂಧಿತ ರೂಪಾಂತರದಲ್ಲಿ 1/2 ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ. ಮಾರ್ಪಡಿಸಿದ ಪಟ್ಟಿ ವೇಳಾಪಟ್ಟಿಯ ಅಂದಾಜು ಅನುಪಾತವು ಅನಿಯಂತ್ರಿತ ರೂಪಾಂತರಕ್ಕೆ 1/2 ಆಗಿದೆ, ಆದರೆ ನಿರ್ಬಂಧಿತ ರೂಪಾಂತರಕ್ಕೆ ಇದು 0 ಆಗಿದೆ (ಇದು ಅನಿಯಂತ್ರಿತವಾಗಿ ಕೆಟ್ಟದ್ದಾಗಿರಬಹುದು). ಮಾರ್ಪಡಿಸಿದ ಎಲ್ಪಿಟಿ ಅಲ್ಗಾರಿದಮ್ನ ಅಂದಾಜು ಅನುಪಾತವು ಗರಿಷ್ಠ 2 ಆಗಿದೆ. ಕೆಳ ಮಿತಿಯು 3/4 ರ ಬಿಗಿಯಾದ ಕೆಟ್ಟ-ಕೇಸ್ ಕಾರ್ಯಕ್ಷಮತೆಯ ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ ಮತ್ತು ಅವರ ಪಿಡಿ ಅಲ್ಗಾರಿದಮ್ 4/3 ರ ಬಿಗಿಯಾದ ಕಾರ್ಯಕ್ಷಮತೆಯ ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ (m ಸಾಕಷ್ಟು ದೊಡ್ಡದಾಗಿದ್ದಾಗ) ಎಂದು ಅವರು ತೋರಿಸುತ್ತಾರೆ. ಅವನು, ಟಾನ್, ಝು ಮತ್ತು ಯಾವೊ ಸಣ್ಣ ಮೊತ್ತವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸುವ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಗಣಿಸುತ್ತಾರೆ. ಫೋಲ್ಡಿಂಗ್ ಅಲ್ಗಾರಿದಮ್ ಬಿಗಿಯಾದ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಅವು ತೋರಿಸುತ್ತವೆ. ಅವರು ಹೊಸ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ, ಹಾರ್ಮೊನಿಕ್ 1, ಕನಿಷ್ಠ ಕೆಟ್ಟ-ಕೇಸ್ ಅನುಪಾತದೊಂದಿಗೆ. ಈ ಎರಡೂ ಕ್ರಮಾವಳಿಗಳು ಕ್ರಮಬದ್ಧವಾಗಿವೆ-ಅವು ವಸ್ತುಗಳನ್ನು ಅವುಗಳ ನಿಖರವಾದ ಮೌಲ್ಯಗಳ ಬದಲಿಗೆ ಅವುಗಳ ನಡುವಿನ ಕ್ರಮದ ಆಧಾರದ ಮೇಲೆ ವಿಭಜಿಸುತ್ತವೆ. ಯಾವುದೇ ಆರ್ಡಿನಲ್ ಅಲ್ಗಾರಿದಮ್ ಚಿಕ್ಕ ಮೊತ್ತವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಲು ಅನುಪಾತವನ್ನು ಹೊಂದಿರುತ್ತದೆ ಎಂದು ಅವು ಸಾಬೀತುಪಡಿಸುತ್ತವೆ. ಇದು ಹಾರ್ಮೊನಿಕ್ 1 ಲಕ್ಷಣರಹಿತವಾಗಿ ಅತ್ಯುತ್ತಮವಾಗಿದೆ ಎಂದು ಸೂಚಿಸುತ್ತದೆ. ಯಾವುದೇ ಸ್ಥಿರ k ಗೆ, ಯಾವುದೇ ಆರ್ಡಿನಲ್ ಅಲ್ಗಾರಿದಮ್ ಸಮೀಕರಣದ ಅತ್ಯಂತ ಚಿಕ್ಕ ಮೂಲ ಅನುಪಾತವನ್ನು ಹೊಂದಿರುತ್ತದೆ. k ಅನಂತಕ್ಕೆ ಒಲವು ತೋರಿದಾಗ, ಈ ಮೇಲಿನ ಮಿತಿಯು 0 ಅನ್ನು ಸಮೀಪಿಸುತ್ತದೆ. ಸಮತೋಲಿತ ಮತ್ತು ಅನಿಯಂತ್ರಿತ ಸಮಸ್ಯೆಗಳ ನಡುವಿನ ಸಂಬಂಧಗಳು ಸಮತೋಲಿತ ವಿಭಜನೆಯ ಸಮಸ್ಯೆ ಮತ್ತು ಪ್ರಮಾಣಿತ (ಅನಿಯಂತ್ರಿತ) ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯ ಅಂದಾಜುಗಳ ನಡುವೆ ಕೆಲವು ಸಾಮಾನ್ಯ ಸಂಬಂಧಗಳಿವೆ. ಬ್ಯಾಬೆಲ್, ಕೆಲ್ಲೆರರ್ ಮತ್ತು ಕೊಟೋವ್ ಅವರು ಅನಿಯಂತ್ರಿತ ಆಪ್ಟಿಮಮ್ ಮತ್ತು ನಿರ್ಬಂಧಿತ ಆಪ್ಟಿಮಮ್ ನಡುವಿನ ಅನುಪಾತವು ಗರಿಷ್ಠವಾಗಿದೆ ಮತ್ತು ಅದು ಬಿಗಿಯಾಗಿದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸುತ್ತಾರೆ. ಕೆಲ್ಲೆರರ್ ಮತ್ತು ಕೊಟೋವ್ ಅವರು ಕೆ ಸಾಮರ್ಥ್ಯ ಮತ್ತು ಅಂದಾಜು-ಅನುಪಾತ ಆರ್ (ಕನಿಷ್ಠ ದೊಡ್ಡ ಮೊತ್ತಕ್ಕೆ) ಯೊಂದಿಗೆ ಸಮತೋಲಿತ ವಿಭಜನೆಗಾಗಿ ಪ್ರತಿ ಶೋಧಕವನ್ನು ಅಂದಾಜು-ಅನುಪಾತದೊಂದಿಗೆ ಅನಿಯಂತ್ರಿತ ವಿಭಜನೆಗಾಗಿ ಶೋಧಕವನ್ನು ಪಡೆಯಲು ಬಳಸಬಹುದು ಎಂದು ಸಾಬೀತುಪಡಿಸುತ್ತಾರೆ. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ತ್ರಿಕೂಟ ವಿಭಜನೆಗಾಗಿ (k = 3) ಅವುಗಳ-ಹೊಂದಾಣಿಕೆ ಕ್ರಮಾವಳಿಯನ್ನು ಅಂದಾಜು-ಅನುಪಾತದೊಂದಿಗೆ ನಿರ್ಬಂಧಿತವಲ್ಲದ ವಿಭಜನೆಗಾಗಿ ಶೋಧಕವನ್ನು ಪಡೆಯಲು ಬಳಸಬಹುದು. ವಿವಿಧ ಕಾರ್ಡಿನಲಿಟಿ ನಿರ್ಬಂಧಗಳು ಪ್ರತಿ ಉಪವಿಭಾಗದ ಮೇಲೆ ವಿಭಿನ್ನ ನಿರ್ಬಂಧವನ್ನು ಅನುಮತಿಸುವ ಮೂಲಕ ಕಾರ್ಡಿನಲಿಟಿ ನಿರ್ಬಂಧಗಳನ್ನು ಸಾಮಾನ್ಯೀಕರಿಸಬಹುದು. ಈ ರೂಪಾಂತರವನ್ನು ಕಿ-ವಿಭಜನೆ ಸಮಸ್ಯೆ ಎಂದು ಕರೆಯುವ "ಮುಕ್ತ ಸಮಸ್ಯೆಗಳು" ವಿಭಾಗದಲ್ಲಿ ಪರಿಚಯಿಸಲಾಗಿದೆ. ಅವರು, ಟಾನ್, ಝು ಮತ್ತು ಯಾವೊ ಅವರು ವಿವಿಧ ಕಾರ್ಡಿನಲಿಟಿ ನಿರ್ಬಂಧಗಳೊಂದಿಗೆ ಚಿಕ್ಕ ಮೊತ್ತವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಲು ಹಾರ್ಮೊನಿಕ್ 2 ಎಂಬ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ಅದರ ಕೆಟ್ಟ-ಪ್ರಕರಣ ಅನುಪಾತವು ಕನಿಷ್ಠವಾಗಿದೆ ಎಂದು ಅವರು ಸಾಬೀತುಪಡಿಸುತ್ತಾರೆ. ಕಾರ್ಡಿನಲಿಟಿಯ ನಿರ್ಬಂಧಗಳನ್ನು ವರ್ಗೀಕರಿಸಲಾಗಿದೆ ಕಾರ್ಡಿನಲಿಟಿಯ ನಿರ್ಬಂಧಗಳ ಮತ್ತೊಂದು ಸಾಮಾನ್ಯೀಕರಣವು ಈ ಕೆಳಗಿನಂತಿದೆ. ಇನ್ಪುಟ್ ಐಟಂಗಳನ್ನು ಕೆ ವರ್ಗಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ. ಪ್ರತಿ ವರ್ಗ ಎಚ್ ಗೆ, ಸಾಮರ್ಥ್ಯದ ನಿರ್ಬಂಧ ಕೆ. ಎಚ್ ಇದೆ. ಎಂ ಉಪಗುಂಪುಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದೂ ಎಚ್ ವರ್ಗದ ಗರಿಷ್ಠ ಕೆ. ಎಚ್ ವಸ್ತುಗಳನ್ನು ಹೊಂದಿರಬಹುದು. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆಃ ಎಲ್ಲಾ ಎಂ ಉಪಗುಂಪುಗಳು ನಿರ್ದಿಷ್ಟ ವಿಭಾಗದ ಮ್ಯಾಟ್ರಾಯಿಡ್ನ ಸ್ವತಂತ್ರ ಗುಂಪಾಗಿರಬೇಕು. ಈ ಸಮಸ್ಯೆಯ ಎರಡು ವಿಶೇಷ ಪ್ರಕರಣಗಳನ್ನು ಅಧ್ಯಯನ ಮಾಡಲಾಗಿದೆ. ಕರ್ನಲ್ ಸಮತೋಲಿತ-ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯಲ್ಲಿ, ಕೆಲವು m ಪೂರ್ವ-ನಿರ್ದಿಷ್ಟ ವಸ್ತುಗಳು ಕರ್ನಲ್ಗಳಾಗಿರುತ್ತವೆ, ಮತ್ತು ಪ್ರತಿಯೊಂದು m ಉಪಗುಂಪುಗಳು ಒಂದೇ ಕರ್ನಲ್ ಅನ್ನು ಹೊಂದಿರಬೇಕು (ಮತ್ತು ಅನಿಯಮಿತ ಸಂಖ್ಯೆಯ ಕರ್ನಲ್ಗಳಲ್ಲದವು). ಇಲ್ಲಿ, ಎರಡು ವರ್ಗಗಳಿವೆಃ ಸಾಮರ್ಥ್ಯ 1 ಹೊಂದಿರುವ ಕರ್ನಲ್ ವರ್ಗ ಮತ್ತು ಅನಿಯಮಿತ ಸಾಮರ್ಥ್ಯ ಹೊಂದಿರುವ ಕರ್ನಲ್ ಅಲ್ಲದ ವರ್ಗ. ಚೆನ್, ಹಿ ಮತ್ತು ಯಾವೊ ಈ ಸಮಸ್ಯೆಯು ಕೆ = 3ಕ್ಕೆ ಸಹ ಎನ್. ಪಿ-ಕಠಿಣವಾಗಿದೆ ಎಂದು ಸಾಬೀತುಪಡಿಸುತ್ತಾರೆ (ಕೆ = 2ಗೆ ಗರಿಷ್ಠ ತೂಕದ ಹೊಂದಾಣಿಕೆಯನ್ನು ಕಂಡುಹಿಡಿಯುವ ಮೂಲಕ ಅದನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಪರಿಹರಿಸಬಹುದು). ನಂತರ ಅವರು ಕರ್ನಲ್-ಎಲ್ಪಿಟಿ (ಕೆಎಲ್ಪಿಟಿ) ಎಂಬ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆಃ ಇದು ಪ್ರತಿ ಉಪಗುಂಪಿಗೆ ಕರ್ನಲ್ ಅನ್ನು ನಿಯೋಜಿಸುತ್ತದೆ, ಮತ್ತು ನಂತರ ಮಾರ್ಪಡಿಸಿದ ಎಲ್ಪಿಟಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ನಡೆಸುತ್ತದೆ (ಪ್ರತಿ ಐಟಂ ಅನ್ನು ಕೆ ಐಟಂಗಳಿಗಿಂತ ಕಡಿಮೆ ಮೊತ್ತದೊಂದಿಗೆ ಉಪಗುಂಪಿನಲ್ಲಿ ಇರಿಸುತ್ತದೆ). ಕೆ = 3 ರೊಂದಿಗೆ, ಕೆ. ಎಲ್. ಪಿ. ಟಿ ಕನಿಷ್ಠ ಅತಿದೊಡ್ಡ ಮೊತ್ತಕ್ಕೆ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಹೊಂದಿದೆ ಎಂದು ಅವರು ಸಾಬೀತುಪಡಿಸುತ್ತಾರೆ. ಆದಾಗ್ಯೂ, ಚೆನ್, ಹಿ ಮತ್ತು ಲಿನ್ ಅದರ ಬಿಗಿಯಾದ ಅಂದಾಜು ಅನುಪಾತವು ಕನಿಷ್ಠ ಅತಿದೊಡ್ಡ ಮೊತ್ತಕ್ಕೆ ಮತ್ತು ಗರಿಷ್ಠ ಚಿಕ್ಕ ಮೊತ್ತಕ್ಕೆ ಎಂದು ಹೇಳುತ್ತಾರೆ. ಈ ಸಮಸ್ಯೆಯ ಮತ್ತೊಂದು ರೂಪಾಂತರದಲ್ಲಿ, m ಗಾತ್ರದ ಕೆಲವು k ವರ್ಗಗಳಿವೆ, ಮತ್ತು ಪ್ರತಿ ಉಪವಿಭಾಗವು ಪ್ರತಿ ವರ್ಗದಿಂದ ನಿಖರವಾಗಿ ಒಂದು ವಸ್ತುವನ್ನು ಹೊಂದಿರಬೇಕು. ಅಂದರೆ, ಪ್ರತಿ ವರ್ಗಕ್ಕೆ ಕೆ. ಎಚ್ = 1. ವೂ ಮತ್ತು ಯಾವೊ ಪದರದ ಎಲ್ಪಿಟಿ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಿದರು-ಇದು ಎಲ್ಪಿಟಿ ಅಲ್ಗಾರಿದಮ್ನ ರೂಪಾಂತರವಾಗಿದೆ. ಅದರ ಅಂದಾಜು ಅನುಪಾತವು ದೊಡ್ಡ ಮೊತ್ತವನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಎಂದು ಅವರು ಸಾಬೀತುಪಡಿಸುತ್ತಾರೆ; ಸಾಮಾನ್ಯ ಸಂದರ್ಭದಲ್ಲಿ ಚಿಕ್ಕ ಮೊತ್ತವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಲು; ಮತ್ತು ಕೆಲವು ವಿಶೇಷ ಸಂದರ್ಭಗಳಲ್ಲಿ, ಸಾಮಾನ್ಯ k ಮತ್ತು k = 3 ಗೆ ಸುಧಾರಿಸಬಹುದು. ಲಿ ಮತ್ತು ಲಿ ಒಂದೇ ಸಮಸ್ಯೆಗೆ ವಿಭಿನ್ನ ಕ್ರಮಾವಳಿಗಳನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಿದರು. ದೊಡ್ಡ ಮೊತ್ತವನ್ನು ಕಡಿಮೆ ಮಾಡಲು, ಅವರು ಸ್ಥಿರಾಂಕ k ಗೆ EPTAS ಅನ್ನು ಮತ್ತು ಸ್ಥಿರಾಂಕ m ಗೆ FPTAS ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ಚಿಕ್ಕ ಮೊತ್ತವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಲು, ಅವರು ಸಾಮಾನ್ಯ ಸಂದರ್ಭದಲ್ಲಿ 1/(k−1) ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಮತ್ತು ಸ್ಥಿರಾಂಕ k ಗೆ EPTAS ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ಅವರು ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ಉದ್ದೇಶವನ್ನು ಸಹ ಅಧ್ಯಯನ ಮಾಡುತ್ತಾರೆಃ ಮೊತ್ತಗಳ ವಾಹಕದ lp-ಮಾನದಂಡವನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು. ಲೇಯರ್ಡ್-ಎಲ್ಪಿಟಿ ಅಲ್ಗಾರಿದಮ್ ಎಲ್ಲಾ ಮಾನದಂಡಗಳಿಗೆ 2-ಅಪ್ರೊಕ್ಸಿಮೇಷನ್ ಅಲ್ಗಾರಿದಮ್ ಎಂದು ಅವರು ಸಾಬೀತುಪಡಿಸುತ್ತಾರೆ. ಡೆಲ್ 'ಒಲ್ಮೋ, ಹ್ಯಾನ್ಸೆನ್, ಪಲ್ಲೋಟ್ಟಿನೊ ಮತ್ತು ಸ್ಟೋರ್ಚಿ ಈ ಸಮಸ್ಯೆಯ 32 ವಿಭಿನ್ನ ಉದ್ದೇಶಗಳನ್ನು ಅಧ್ಯಯನ ಮಾಡುತ್ತಾರೆ. ನಾಲ್ಕು ಆಪರೇಟರ್ಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದಕ್ಕೂ ಗರಿಷ್ಠ, ಕನಿಷ್ಠ, ಮೊತ್ತ, ವ್ಯತ್ಯಾಸ, ಪ್ರತಿ ಉಪವಿಭಾಗದೊಳಗಿನ ಕೆ ಐಟಂಗಳಿಗೆ ಒಬ್ಬ ಆಪರೇಟರ್ ಅನ್ನು ಅನ್ವಯಿಸಬಹುದು, ಮತ್ತು ನಂತರ ವಿವಿಧ ಉಪಗುಂಪುಗಳಿಗೆ ಎಂ ಫಲಿತಾಂಶಗಳಿಗೆ ಒಬ್ಬ ಆಪರೇಟರ್ ಅನ್ನು ಅನ್ವಯಿಸಬಹುದು. ಈ 16 ಉದ್ದೇಶಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಬಹುದು ಅಥವಾ ಕನಿಷ್ಠಗೊಳಿಸಬಹುದು, ಒಟ್ಟು 32. ಇವುಗಳಲ್ಲಿ 21 ಸಮಸ್ಯೆಗಳನ್ನು ರೇಖೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು ಎಂದು ಅವು ತೋರಿಸುತ್ತವೆ; 7ಕ್ಕೆ ಹೆಚ್ಚು ಸಂಕೀರ್ಣವಾದ, ಆದರೆ ಇನ್ನೂ ಬಹುಪದ-ಸಮಯದ, ಕ್ರಮಾವಳಿಗಳು ಬೇಕಾಗುತ್ತವೆ; 3 ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿವೆಃ ಗರಿಷ್ಠಗೊಳಿಸುವುದು (ಕನಿಷ್ಠ, ಮೊತ್ತ), ಕನಿಷ್ಠಗೊಳಿಸುವುದು (ಗರಿಷ್ಠ, ಮೊತ್ತ) ಮತ್ತು ಕನಿಷ್ಠಗೊಳಿಸುವುದು (ವ್ಯತ್ಯಾಸ, ಮೊತ್ತ). ಅವರು ಕನಿಷ್ಠಗೊಳಿಸುವ ಸ್ಥಿತಿಯನ್ನು (ಡಿಫ್, ಡಿಫ್) ತೆರೆದಿಟ್ಟರು. ಮ್ಯಾಟ್ರಾಯಿಡ್-ನಿರ್ಬಂಧಿತ ಸಂಖ್ಯೆ ವಿಭಜನೆಯು ಒಂದು ಸಾಮಾನ್ಯೀಕರಣವಾಗಿದ್ದು, ಇದರಲ್ಲಿ ಸ್ಥಿರ ಮ್ಯಾಟ್ರಾಯಿಡ್ ಅನ್ನು ನಿಯತಾಂಕವಾಗಿ ನೀಡಲಾಗುತ್ತದೆ, ಮತ್ತು ಪ್ರತಿಯೊಂದು m ಉಪಗುಂಪುಗಳು ಈ ಮ್ಯಾಟ್ರಾಯಿಡ್ನ ಸ್ವತಂತ್ರ ಸೆಟ್ ಅಥವಾ ಬೇಸ್ ಆಗಿರಬೇಕು. ಕಾರ್ಡಿನಲಿಟಿ ನಿರ್ಬಂಧಗಳು ಮ್ಯಾಟ್ರಾಯಿಡ್ ನಿರ್ಬಂಧಗಳ ವಿಶೇಷ ಪ್ರಕರಣಗಳಾಗಿವೆ, ಇದರಲ್ಲಿ ಮ್ಯಾಟ್ರಾಯಿಡ್ ಏಕರೂಪದ ಮ್ಯಾಟ್ರಾಯಿಡ್ ಆಗಿದೆ. ವರ್ಗೀಕರಿಸಿದ ಕಾರ್ಡಿನಲಿಟಿ ನಿರ್ಬಂಧಗಳು ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದ್ದು, ಇದರಲ್ಲಿ ಮ್ಯಾಟ್ರಾಯಿಡ್ ಒಂದು ಪಾರ್ಟಿಷನ್ ಮ್ಯಾಟ್ರಾಯಿಡ್ ಆಗಿದೆ. ಉಲ್ಲೇಖಗಳ ಸಂಖ್ಯೆ ವಿಭಜನೆ