Matroid-constrained number partitioning
ಮ್ಯಾಟ್ರಾಯಿಡ್-ನಿರ್ಬಂಧಿತ ಸಂಖ್ಯೆ ವಿಭಜನೆಯು ಬಹುಮಾರ್ಗ ಸಂಖ್ಯೆ ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯ ಒಂದು ರೂಪಾಂತರವಾಗಿದೆ, ಇದರಲ್ಲಿ ವಿಭಾಗದಲ್ಲಿನ ಉಪಗುಂಪುಗಳು ಮ್ಯಾಟ್ರಾಯಿಡ್ನ ಸ್ವತಂತ್ರ ಸೆಟ್ಗಳಾಗಿರಬೇಕು. ಈ ಸಮಸ್ಯೆಯ ಒಳಹರಿವು ವಸ್ತುಗಳ ಒಂದು ಸೆಟ್ S, ಧನಾತ್ಮಕ ಪೂರ್ಣಾಂಕ m, ಮತ್ತು ಅದೇ ಸೆಟ್ S ಮೇಲೆ ಕೆಲವು m ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳು. S ಅನ್ನು m ಉಪಗುಂಪುಗಳಾಗಿ ವಿಭಜಿಸುವುದು ಗುರಿಯಾಗಿದೆ, ಅಂದರೆ ಪ್ರತಿ ಉಪಗುಂಪು i ಮ್ಯಾಟ್ರೋಯಿಡ್ i ನಲ್ಲಿ ಸ್ವತಂತ್ರ ಸೆಟ್ ಆಗಿದೆ. ಈ ನಿರ್ಬಂಧಕ್ಕೆ ಒಳಪಟ್ಟು, ಕೆಲವು ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯಗಳನ್ನು ಕನಿಷ್ಠಗೊಳಿಸಬೇಕು, ಉದಾಹರಣೆಗೆ, ಉಪಗುಂಪಿನಲ್ಲಿ ಅತಿದೊಡ್ಡ ಮೊತ್ತದ ಐಟಂ ಗಾತ್ರಗಳನ್ನು ಕನಿಷ್ಠಗೊಳಿಸುವುದು. ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾದ ರೂಪಾಂತರದಲ್ಲಿ, ಪ್ರತಿಯೊಂದು ಎಮ್ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳು ತೂಕದ ಕಾರ್ಯವನ್ನು ಹೊಂದಿವೆ, ಇದು ಗ್ರೌಂಡ್-ಸೆಟ್ನ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ತೂಕವನ್ನು ನಿಗದಿಪಡಿಸುತ್ತದೆ. ವಿವಿಧ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯಗಳನ್ನು ಪರಿಗಣಿಸಲಾಗಿದೆ. ಗರಿಷ್ಠ, ಕನಿಷ್ಠ, ಮೊತ್ತ ಎಂಬ ಮೂರು ಆಪರೇಟರ್ಗಳಲ್ಲಿ ಪ್ರತಿಯೊಂದಕ್ಕೂ, ಪ್ರತಿ ಉಪವಿಭಾಗದಲ್ಲಿರುವ ವಸ್ತುಗಳ ತೂಕದ ಮೇಲೆ ಮತ್ತು ಉಪಗುಂಪುಗಳ ಮೇಲೆ ಈ ಆಪರೇಟರ್ ಅನ್ನು ಬಳಸಬಹುದು. ಒಟ್ಟಾರೆಯಾಗಿ, 9 ಸಂಭವನೀಯ ವಸ್ತುನಿಷ್ಠ ಕಾರ್ಯಗಳಿವೆ, ಪ್ರತಿಯೊಂದನ್ನೂ ಗರಿಷ್ಠಗೊಳಿಸಬಹುದು ಅಥವಾ ಕನಿಷ್ಠಗೊಳಿಸಬಹುದು. ವಿಶೇಷ ಪ್ರಕರಣಗಳು ಮ್ಯಾಟ್ರಾಯಿಡ್-ನಿರ್ಬಂಧಿತ ವಿಭಜನೆಯ ಸಮಸ್ಯೆಗಳ ಕೆಲವು ಪ್ರಮುಖ ವಿಶೇಷ ಪ್ರಕರಣಗಳೆಂದರೆಃ (ಗರಿಷ್ಠ, ಮೊತ್ತ) ಉದ್ದೇಶವು ಎಲ್ಲಾ ಉಪಗುಂಪುಗಳ ಮೇಲೆ, ಉಪಗುಂಪಿನಲ್ಲಿನ ಒಟ್ಟು ತೂಕದ ಗರಿಷ್ಠವಾಗಿರುತ್ತದೆ. ವಸ್ತುಗಳು ಉದ್ಯೋಗಗಳನ್ನು ಪ್ರತಿನಿಧಿಸಿದಾಗ ಮತ್ತು ತೂಕಗಳು ಅವುಗಳ ಉದ್ದವನ್ನು ಪ್ರತಿನಿಧಿಸಿದಾಗ, ಈ ಉದ್ದೇಶವು ಕೇವಲ ವೇಳಾಪಟ್ಟಿಯ ನಿರ್ಮಾಣವಾಗಿದೆ. ಆದ್ದರಿಂದ, ಈ ಉದ್ದೇಶವನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಮ್ಯಾಟ್ರಾಯಿಡ್ ನಿರ್ಬಂಧಗಳ ಅಡಿಯಲ್ಲಿ ಮೇಕ್ಸ್ಪ್ಯಾನ್ ಅನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಸಮನಾಗಿರುತ್ತದೆ. ಗರಿಷ್ಠಗೊಳಿಸುವ ಎರಡು ಗುರಿಗಳನ್ನು (ಕನಿಷ್ಠ, ಮೊತ್ತ) ಸಹ ಈ ಸಂದರ್ಭದಲ್ಲಿ ಅಧ್ಯಯನ ಮಾಡಲಾಗಿದೆ. ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳು ಮುಕ್ತ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳಾಗಿರುವ (ಯಾವುದೇ ನಿರ್ಬಂಧಗಳಿಲ್ಲ) ಮತ್ತು ಎಂ ತೂಕ-ಕಾರ್ಯಗಳು ಒಂದೇ ಆಗಿರುವ ವಿಶೇಷ ಪ್ರಕರಣವು ಒಂದೇ ರೀತಿಯ ಯಂತ್ರಗಳ ವೇಳಾಪಟ್ಟಿಗೆ ಅನುರೂಪವಾಗಿದೆ, ಇದನ್ನು ಬಹುಮಾರ್ಗ ಸಂಖ್ಯೆ ವಿಭಜನೆ ಎಂದೂ ಕರೆಯಲಾಗುತ್ತದೆ. ಉಚಿತ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳು ಮತ್ತು ವಿವಿಧ ತೂಕ-ಕಾರ್ಯಗಳ ಪ್ರಕರಣವು ಸಂಬಂಧವಿಲ್ಲದ-ಯಂತ್ರಗಳ ವೇಳಾಪಟ್ಟಿಗೆ ಅನುರೂಪವಾಗಿದೆ. ಏಕರೂಪದ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳ ವಿಶೇಷ ಪ್ರಕರಣವು ಉಪಗುಂಪುಗಳ ಮೇಲಿನ ಕಾರ್ಡಿನಲಿಟಿ ನಿರ್ಬಂಧಗಳಿಗೆ ಅನುರೂಪವಾಗಿದೆ. ವಿಭಜನೆಯ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳ ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ಪ್ರಕರಣವು ವರ್ಗೀಕರಿಸಿದ ಕಾರ್ಡಿನಲಿಟಿ ನಿರ್ಬಂಧಗಳಿಗೆ ಅನುರೂಪವಾಗಿದೆ. ಈ ಸಮಸ್ಯೆಗಳನ್ನು ಸಮತೋಲಿತ ಸಂಖ್ಯೆ ವಿಭಜನೆಯ ಪುಟದಲ್ಲಿ ವಿವರಿಸಲಾಗಿದೆ. (ಮೊತ್ತ, ಮೊತ್ತ) ಉದ್ದೇಶವು ಎಲ್ಲಾ ಉಪಗುಂಪುಗಳಲ್ಲಿನ ಎಲ್ಲಾ ವಸ್ತುಗಳ ತೂಕದ ಮೊತ್ತವಾಗಿದೆ, ಅಲ್ಲಿ ಪ್ರತಿ ಉಪಗುಂಪು i ನಲ್ಲಿನ ತೂಕವನ್ನು ಮ್ಯಾಟ್ರಾಯಿಡ್ i ನ ತೂಕ-ಕಾರ್ಯದಿಂದ ಲೆಕ್ಕಹಾಕಲಾಗುತ್ತದೆ. ಈ ಉದ್ದೇಶವನ್ನು ಕಡಿಮೆ ಮಾಡುವುದನ್ನು ತೂಕದ ಮ್ಯಾಟ್ರಾಯಿಡ್ ಛೇದಕ ಸಮಸ್ಯೆಗೆ ಇಳಿಸಬಹುದು-ಎರಡು ಮ್ಯಾಟ್ರಾಯಿಡ್ಗಳಲ್ಲಿ ಏಕಕಾಲದಲ್ಲಿ ಸ್ವತಂತ್ರವಾಗಿರುವ ಗರಿಷ್ಠ-ತೂಕದ ಉಪವಿಭಾಗವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು. ಈ ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು. (ಗರಿಷ್ಠ, ಗರಿಷ್ಠ) ಉದ್ದೇಶವು ಎಲ್ಲಾ ಉಪಗುಂಪುಗಳಲ್ಲಿನ ಗರಿಷ್ಠ ತೂಕವಾಗಿದೆ, ಅಲ್ಲಿ ಪ್ರತಿ ಉಪಗುಂಪು i ನಲ್ಲಿನ ತೂಕವನ್ನು ಮ್ಯಾಟ್ರಾಯಿಡ್ i ನ ತೂಕ-ಕಾರ್ಯದಿಂದ ಲೆಕ್ಕಹಾಕಲಾಗುತ್ತದೆ. ಗ್ರಾಫಿಕ್ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳೊಂದಿಗೆ ಈ ಉದ್ದೇಶವನ್ನು ಕಡಿಮೆ ಮಾಡುವುದನ್ನು ಮರದ ಸಮಸ್ಯೆಯ ಕನಿಷ್ಠ ಅಡಚಣೆಯನ್ನು ಪರಿಹರಿಸಲು ಬಳಸಬಹುದು. (ಮೊತ್ತ, ಕನಿಷ್ಠ) ಉದ್ದೇಶವು ಎಲ್ಲಾ ಉಪಗುಂಪುಗಳಲ್ಲಿನ ಕನಿಷ್ಠ ತೂಕಗಳ ಮೊತ್ತವಾಗಿದೆ. ಈ ಉದ್ದೇಶವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸಲು, ಕೆ ಒಂದೇ ರೀತಿಯ ಚಿತ್ರಾತ್ಮಕ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳೊಂದಿಗೆ, ಮರದ ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯನ್ನು ವಿಸ್ತರಿಸುವ ಗರಿಷ್ಠ ಒಟ್ಟು ಸಾಮರ್ಥ್ಯವನ್ನು ಪರಿಹರಿಸಲು ಬಳಸಬಹುದು. (ಮೊತ್ತ, ಗರಿಷ್ಠ) ಉದ್ದೇಶವು ಎಲ್ಲಾ ಉಪಗುಂಪುಗಳಲ್ಲಿನ ಗರಿಷ್ಠ ತೂಕಗಳ ಮೊತ್ತವಾಗಿದೆ. ಈ ಉದ್ದೇಶವು ವೇಳಾಪಟ್ಟಿಗೆ ಅಗತ್ಯವಿರುವ ಒಟ್ಟು ಸ್ಮರಣೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ, ಪ್ರತಿ ಮ್ಯಾಟ್ರಾಯಿಡ್ i ಯಂತ್ರದಲ್ಲಿ ಕಾರ್ಯಸಾಧ್ಯವಾದ ಹಂಚಿಕೆಯನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಸಾಮಾನ್ಯ ಮ್ಯಾಟ್ರಾಯಿಡ್ ನಿರ್ಬಂಧಗಳನ್ನು ಮೊದಲು ಬರ್ಕಾರ್ಡ್ ಮತ್ತು ಯಾವೊ ಪರಿಗಣಿಸಿದರು. ಪಾರ್ಟಿಷನ್ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳ ಉಪವರ್ಗಕ್ಕಾಗಿ ದುರಾಸೆಯ ಅಲ್ಗಾರಿದಮ್ ಮೂಲಕ ಬಹುಪದ ಸಮಯದಲ್ಲಿ ಕನಿಷ್ಠಗೊಳಿಸುವಿಕೆಯನ್ನು (ಮೊತ್ತ, ಗರಿಷ್ಠ) ಮಾಡಬಹುದು ಎಂದು ಅವರು ತೋರಿಸಿದರು. ಹ್ವಾಂಗ್ ಮತ್ತು ರೋಥ್ಬ್ಲಮ್ ಪರ್ಯಾಯ ಸಾಕಷ್ಟು ಸ್ಥಿತಿಯನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಿದರು. ವೂ ಮತ್ತು ಯಾವೊ ಸಾಮಾನ್ಯ ಮ್ಯಾಟ್ರಾಯಿಡ್ ನಿರ್ಬಂಧಗಳೊಂದಿಗೆ ಕನಿಷ್ಠಗೊಳಿಸಲು (ಗರಿಷ್ಠ, ಮೊತ್ತ) ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸಿದರು. ಅಬ್ಬಾಸ್ಸಿ, ಮಿರ್ರೋಕ್ನಿ ಮತ್ತು ಠಾಕೂರ್ ಅವರು ಮ್ಯಾಟ್ರಾಯಿಡ್ ನಿರ್ಬಂಧಗಳ ಅಡಿಯಲ್ಲಿ ವೈವಿಧ್ಯತೆಯ ಗರಿಷ್ಠಗೊಳಿಸುವಿಕೆಯ ಸಮಸ್ಯೆಗೆ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುತ್ತಾರೆ. ಕವಾಸೆ, ಕಿಮುರಾ, ಮಾಕಿನೋ ಮತ್ತು ಸುಮಿತಾ ಅವರು ಗರಿಷ್ಠಗೊಳಿಸುವ ಸಮಸ್ಯೆಗಳನ್ನು ಕನಿಷ್ಠಗೊಳಿಸುವ ಸಮಸ್ಯೆಗಳಿಗೆ ಕಡಿಮೆ ಮಾಡಬಹುದು ಎಂದು ತೋರಿಸುತ್ತಾರೆ. ನಂತರ, ಅವರು ಏಳು ಕನಿಷ್ಠಗೊಳಿಸುವ ಸಮಸ್ಯೆಗಳನ್ನು ವಿಶ್ಲೇಷಿಸುತ್ತಾರೆಃ ಕನಿಷ್ಠಗೊಳಿಸುವುದು (ಮೊತ್ತ, ಗರಿಷ್ಠ): ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳು ಮತ್ತು ತೂಕಗಳು ಒಂದೇ ಆಗಿದ್ದರೂ ಸಹ ಸಮಸ್ಯೆಯು ಬಲವಾಗಿ ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿರುತ್ತದೆ. ಒಂದೇ ರೀತಿಯ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳು ಮತ್ತು ತೂಕಗಳಿಗೆ ಪಿಟಿಎಎಸ್ ಇದೆ. ಸಾಮಾನ್ಯ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳು ಮತ್ತು ತೂಕಗಳಿಗೆ, ಯಾವುದೇ ε> 0 ಗೆ εm-ಅಪ್ರೊಕ್ಸಿಮೇಷನ್ ಅಲ್ಗಾರಿದಮ್ ಇದೆ. ಇದು O (ಲಾಗ್ m) ಅಂಶದೊಂದಿಗೆ ಅಂದಾಜು ಮಾಡಲು NP-ಕಠಿಣವಾಗಿದೆ. ಕನಿಷ್ಠಗೊಳಿಸುವುದು (ಕನಿಷ್ಠ, ಕನಿಷ್ಠ), (ಗರಿಷ್ಠ, ಗರಿಷ್ಠ), (ಕನಿಷ್ಠ, ಗರಿಷ್ಠ) ಮತ್ತು (ಕನಿಷ್ಠ, ಮೊತ್ತ): ಬಹುಪದ-ಸಮಯದ ಕ್ರಮಾವಳಿಗಳಿವೆ. ಅವರು ಮ್ಯಾಟ್ರಾಯಿಡ್ ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯ ಕಾರ್ಯಸಾಧ್ಯತೆಯ ಸಮಸ್ಯೆಗೆ ಸಮಸ್ಯೆಗಳನ್ನು ಕಡಿಮೆ ಮಾಡುತ್ತಾರೆ. ಕನಿಷ್ಠಗೊಳಿಸುವುದು (ಗರಿಷ್ಠ, ಕನಿಷ್ಠ) ಮತ್ತು (ಮೊತ್ತ, ಕನಿಷ್ಠ): ಒಂದೇ ರೀತಿಯ ಮ್ಯಾಟ್ರೋಯಿಡ್ಗಳು ಮತ್ತು ತೂಕಗಳಿಗೆ ಬಹುಪದ-ಸಮಯದ ಕ್ರಮಾವಳಿಗಳಿವೆ. ಸಾಮಾನ್ಯ ಸಂದರ್ಭದಲ್ಲಿ, ಇದು ಬಲವಾಗಿ ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿದ್ದು, ಅಂದಾಜು ಕೂಡ ಆಗಿರುತ್ತದೆ. ಇತರ ಎರಡು ಸಮಸ್ಯೆಗಳನ್ನು ಹಿಂದಿನ ಕೃತಿಗಳಲ್ಲಿ ವಿಶ್ಲೇಷಿಸಲಾಗಿದೆಃ ಕನಿಷ್ಠಗೊಳಿಸುವುದು (ಗರಿಷ್ಠ, ಮೊತ್ತ) ಬಲವಾಗಿ ಎನ್. ಪಿ-ಹಾರ್ಡ್ ಎಂದು ತಿಳಿದುಬಂದಿದೆ (3-ವಿಭಾಗವು ವಿಶೇಷ ಪ್ರಕರಣವಾಗಿದೆ), ಮತ್ತು ಕನಿಷ್ಠಗೊಳಿಸುವುದನ್ನು (ಮೊತ್ತ, ಮೊತ್ತ) ತೂಕದ ಮ್ಯಾಟ್ರಾಯಿಡ್ ಛೇದಕಕ್ಕೆ ಕಡಿಮೆ ಮಾಡಬಹುದು, ಇದು ಬಹುಪದವಾಗಿದೆ. ಸಂಬಂಧಿತ ಸಮಸ್ಯೆಗಳು ಮ್ಯಾಟ್ರಾಯಿಡ್ ವಿಭಜನೆಯು ಬೇರೆ ಸಮಸ್ಯೆಯಾಗಿದೆ, ಇದರಲ್ಲಿ ಭಾಗಗಳ ಸಂಖ್ಯೆ m ಅನ್ನು ನಿಗದಿಪಡಿಸಲಾಗಿಲ್ಲ. ಒಂದೇ ಮ್ಯಾಟ್ರಾಯಿಡ್ ಇದೆ, ಮತ್ತು ಅದರ ಅಂಶಗಳನ್ನು ಸಣ್ಣ ಸಂಖ್ಯೆಯ ಸ್ವತಂತ್ರ ಸೆಟ್ಗಳಾಗಿ ವಿಂಗಡಿಸುವುದು ಗುರಿಯಾಗಿದೆ. ಉಲ್ಲೇಖಗಳು ಮ್ಯಾಟ್ರಾಯಿಡ್ ಸಿದ್ಧಾಂತ ಸಂಖ್ಯೆ ವಿಭಜನೆ