Maximum cut
ಗ್ರಾಫ್ಗೆ, ಗರಿಷ್ಠ ಕಟ್ ಎಂದರೆ ಅದರ ಗಾತ್ರವು ಕನಿಷ್ಠ ಇತರ ಯಾವುದೇ ಕಟ್ನ ಗಾತ್ರವಾಗಿರುತ್ತದೆ. ಅಂದರೆ, ಇದು ಗ್ರಾಫ್ನ ಶೃಂಗಗಳನ್ನು ಎರಡು ಪೂರಕ ಸೆಟ್ಗಳಾಗಿ ವಿಂಗಡಿಸುತ್ತದೆ ಮತ್ತು ಅವುಗಳ ನಡುವಿನ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು ಸಾಧ್ಯವಾದಷ್ಟು ದೊಡ್ಡದಾಗಿದೆ. ಅಂತಹ ಕಡಿತವನ್ನು ಕಂಡುಹಿಡಿಯುವುದನ್ನು ಗರಿಷ್ಠ-ಕಡಿತ ಸಮಸ್ಯೆ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಸಮಸ್ಯೆಯನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಸರಳವಾಗಿ ಹೇಳಬಹುದು. ಒಬ್ಬರು ಶೃಂಗದ ಗುಂಪಿನ ಉಪವಿಭಾಗವನ್ನು ಬಯಸುತ್ತಾರೆ, ಅದು ಮತ್ತು ಪೂರಕ ಉಪವಿಭಾಗದ ನಡುವಿನ ಅಂಚುಗಳ ಸಂಖ್ಯೆಯು ಸಾಧ್ಯವಾದಷ್ಟು ದೊಡ್ಡದಾಗಿರುತ್ತದೆ. ಸಮಾನವಾಗಿ, ಸಾಧ್ಯವಾದಷ್ಟು ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ಗ್ರಾಫ್ನ ಉಭಯಪಕ್ಷೀಯ ಉಪಗ್ರ್ಯಾಫ್ ಅನ್ನು ಬಯಸುತ್ತಾರೆ. ತೂಕದ ಮ್ಯಾಕ್ಸ್-ಕಟ್ ಎಂಬ ಸಮಸ್ಯೆಯ ಹೆಚ್ಚು ಸಾಮಾನ್ಯ ಆವೃತ್ತಿಯಿದೆ, ಅಲ್ಲಿ ಪ್ರತಿ ಅಂಚು ನೈಜ ಸಂಖ್ಯೆ, ಅದರ ತೂಕದೊಂದಿಗೆ ಸಂಬಂಧಿಸಿದೆ ಮತ್ತು ಅಂಚುಗಳ ಸಂಖ್ಯೆಗಿಂತ ಅದರ ಮತ್ತು ಅದರ ಪೂರಕಗಳ ನಡುವಿನ ಅಂಚುಗಳ ಒಟ್ಟು ತೂಕವನ್ನು ಗರಿಷ್ಠಗೊಳಿಸುವುದು ಇದರ ಉದ್ದೇಶವಾಗಿದೆ. ಧನಾತ್ಮಕ ಮತ್ತು ಋಣಾತ್ಮಕ ತೂಕಗಳೆರಡಕ್ಕೂ ಅವಕಾಶ ನೀಡುವ ತೂಕದ ಗರಿಷ್ಠ-ಕಡಿತ ಸಮಸ್ಯೆಯನ್ನು ಎಲ್ಲಾ ತೂಕಗಳಲ್ಲಿ ಚಿಹ್ನೆಯನ್ನು ತಿರುಗಿಸುವ ಮೂಲಕ ತೂಕದ ಕನಿಷ್ಠ ಕಡಿತ ಸಮಸ್ಯೆಯಾಗಿ ಪರಿವರ್ತಿಸಬಹುದು. ಎಡ್ವರ್ಡ್ಸ್ ಈ ಕೆಳಗಿನ ಎರಡು ಕೆಳ ಮಿತಿಯನ್ನು ಮ್ಯಾಕ್ಸ್-ಕಟ್ಗೆ ಶೃಂಗಗಳು ಮತ್ತು ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ರೇಖಾಚಿತ್ರದಲ್ಲಿ ಪಡೆದರು ((ಎ) ಅನಿಯಂತ್ರಿತವಾಗಿದೆ, ಆದರೆ (ಬಿ) ಇದು ಸಂಪರ್ಕಗೊಂಡಿದೆ): (ಎ) (ಬಿ) ಬೌಂಡ್ (ಬಿ) ಅನ್ನು ಎರ್ಡೋಸ್ ಊಹಿಸಿದಂತೆ ಎಡ್ವರ್ಡ್ಸ್-ಎರ್ಡೋಸ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಎಡ್ವರ್ಡ್ಸ್-ಎರ್ಡೋಸ್ ಸಂಭಾವ್ಯ ವಿಧಾನವನ್ನು ಬಳಸಿಕೊಂಡು ಬಂಧಿಸಲ್ಪಟ್ಟಿದ್ದಾರೆ ಎಂದು ಎಡ್ವರ್ಡ್ಸ್ ಸಾಬೀತುಪಡಿಸಿದರು; ಕ್ರೌಸ್ಟನ್ ಮತ್ತು ಇತರರು. ರೇಖೀಯ ಬೀಜಗಣಿತ ಮತ್ತು ಸೂಡೊ-ಬೂಲಿಯನ್ ಕಾರ್ಯಗಳ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಬಳಸಿಕೊಂಡು ಬಂಧವನ್ನು ಸಾಬೀತುಪಡಿಸಲಾಗಿದೆ. ಕ್ರೌಸ್ಟನ್ ಮತ್ತು ಇತರರ ಪುರಾವೆ. ಎಡ್ವರ್ಡ್ಸ್-ಎರ್ಡೋಸ್ ಅನ್ನು ಸಮತೋಲಿತ ಸಬ್ಗ್ರಾಫ್ ಸಮಸ್ಯೆ (ಬಿಎಸ್ಪಿ) ಗೆ ಬದ್ಧವಾಗಿ ಸಹಿ ಮಾಡಿದ ಗ್ರಾಫ್ಗಳಲ್ಲಿ ವಿಸ್ತರಿಸಲು ನಮಗೆ ಅನುಮತಿಸುತ್ತದೆ, ಅಂದರೆ. ಪ್ರತಿ ಅಂಚನ್ನು + ಅಥವಾ-ಎಂದು ನಿಗದಿಪಡಿಸಲಾಗಿರುವ ರೇಖಾಚಿತ್ರಗಳು. ಉಪಗುಂಪುಗಳಾಗಿ ವಿಂಗಡಿಸಲು ಮತ್ತು, ಎರಡೂ ಮತ್ತು ಮತ್ತು ಒಂದೇ ಉಪಗುಂಪಿನಲ್ಲಿದ್ದರೆ, ಅಥವಾ ಮತ್ತು ಮತ್ತು ವಿಭಿನ್ನ ಉಪಗುಂಪುಗಳಾಗಿದ್ದರೆ ಅಂಚನ್ನು ಸಮತೋಲನಗೊಳಿಸಲಾಗುತ್ತದೆ. ಬಿಎಸ್ಪಿ ಗರಿಷ್ಠ ಸಂಖ್ಯೆಯ ಸಮತೋಲಿತ ಅಂಚುಗಳನ್ನು ಹೊಂದಿರುವ ವಿಭಾಗವನ್ನು ಕಂಡುಹಿಡಿಯುವ ಗುರಿಯನ್ನು ಹೊಂದಿದೆ. ಎಡ್ವರ್ಡ್ಸ್-ಎರ್ಡೋಸ್ ಪ್ರತಿ ಸಂಪರ್ಕಿತ ಸಹಿ ಗ್ರಾಫ್ಗೆ ಕಡಿಮೆ ಮಿತಿಯನ್ನು ನೀಡುತ್ತದೆ. ಗ್ರಾಫ್ಗಳ ವಿಶೇಷ ವರ್ಗಗಳಿಗೆ ಬೌಂಡ್ (ಎ) ಅನ್ನು ಸುಧಾರಿಸಲಾಗಿದೆಃ ತ್ರಿಕೋನ-ಮುಕ್ತ ಗ್ರಾಫ್ಗಳು, ನೀಡಲಾದ ಗರಿಷ್ಠ ಮಟ್ಟದ ಗ್ರಾಫ್ಗಳು,-ಮುಕ್ತ ಗ್ರಾಫ್ಗಳು, ಇತ್ಯಾದಿ. ಪೊಲ್ಜಾಕ್ ಮತ್ತು ತುರ್ಜಿಕ್ ಎಡ್ವರ್ಡ್ಸ್-ಎರ್ಡೋಸ್ ಅನ್ನು ತೂಕದ ಮ್ಯಾಕ್ಸ್-ಕಟ್ಗೆ ವಿಸ್ತರಿಸಿದರುಃ ಅಲ್ಲಿ ಮತ್ತು ಅದರ ತೂಕ ಮತ್ತು ಅದರ ಕನಿಷ್ಠ ತೂಕದ ಮರ. ಇತ್ತೀಚೆಗೆ, ಗುಟಿನ್ ಮತ್ತು ಯೆಯೋ ಅವರು ಪೋಲ್ಜಕ್-ತುರ್ಜಿಕ್ ಅನ್ನು ವಿಸ್ತರಿಸುವ ತೂಕದ ಮ್ಯಾಕ್ಸ್-ಕಟ್ಗಾಗಿ ಅನಿಯಂತ್ರಿತ ತೂಕದ ಗ್ರಾಫ್ಗಳಿಗೆ ಮತ್ತು ವಿಶೇಷ ವರ್ಗದ ತೂಕದ ಗ್ರಾಫ್ಗಳಿಗೆ ಮಿತಿಗಳನ್ನು ವಿಸ್ತರಿಸಲು ಹಲವಾರು ಕಡಿಮೆ ಮಿತಿಗಳನ್ನು ಪಡೆದರು. ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಂಕೀರ್ಣತೆ ಗರಿಷ್ಠ ಕಡಿತಕ್ಕೆ ಸಂಬಂಧಿಸಿದ ಈ ಕೆಳಗಿನ ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯನ್ನು ಸೈದ್ಧಾಂತಿಕ ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನದಲ್ಲಿ ವ್ಯಾಪಕವಾಗಿ ಅಧ್ಯಯನ ಮಾಡಲಾಗಿದೆಃ ಗ್ರಾಫ್ ಜಿ ಮತ್ತು ಪೂರ್ಣಾಂಕ ಕೆ ಅನ್ನು ನೀಡಿದರೆ, ಜಿ ಯಲ್ಲಿ ಕನಿಷ್ಠ ಕೆ ಗಾತ್ರದ ಕಡಿತವಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸಿ. ಈ ಸಮಸ್ಯೆಯನ್ನು ಎನ್ಪಿ-ಪೂರ್ಣ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಸಮಸ್ಯೆಯು ಎನ್. ಪಿ. ಯಲ್ಲಿದೆ ಎಂಬುದನ್ನು ಸುಲಭವಾಗಿ ಕಾಣಬಹುದುಃ ಸಾಕಷ್ಟು ದೊಡ್ಡ ಕಟ್ ಅನ್ನು ಪ್ರಸ್ತುತಪಡಿಸುವ ಮೂಲಕ ಹೌದು ಉತ್ತರವನ್ನು ಸಾಬೀತುಪಡಿಸುವುದು ಸುಲಭ. ಸಮಸ್ಯೆಯ ಎನ್. ಪಿ.-ಪೂರ್ಣತೆಯನ್ನು ತೋರಿಸಬಹುದು, ಉದಾಹರಣೆಗೆ, ಗರಿಷ್ಠ 2-ತೃಪ್ತಿಯಿಂದ ಕಡಿತಗೊಳಿಸುವುದು (ಗರಿಷ್ಠ ತೃಪ್ತಿಯ ಸಮಸ್ಯೆಯ ನಿರ್ಬಂಧ). ನಿರ್ಧಾರದ ಸಮಸ್ಯೆಯ ತೂಕದ ಆವೃತ್ತಿಯು ಕಾರ್ಪ್ನ 21 ಎನ್ಪಿ-ಪೂರ್ಣ ಸಮಸ್ಯೆಗಳಲ್ಲಿ ಒಂದಾಗಿತ್ತು; ಕಾರ್ಪ್ ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯಿಂದ ಕಡಿಮೆಯಾಗುವ ಮೂಲಕ ಎನ್ಪಿ-ಪೂರ್ಣತೆಯನ್ನು ತೋರಿಸಿದರು. ಮೇಲಿನ ನಿರ್ಧಾರ ಸಮಸ್ಯೆಯ ಕ್ಯಾನೊನಿಕಲ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ರೂಪಾಂತರವನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಮ್ಯಾಕ್ಸಿಮಮ್-ಕಟ್ ಪ್ರಾಬ್ಲಮ್ ಅಥವಾ ಮ್ಯಾಕ್ಸ್-ಕಟ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ ಮತ್ತು ಇದನ್ನು ಹೀಗೆ ವ್ಯಾಖ್ಯಾನಿಸಲಾಗಿದೆಃ ಗ್ರಾಫ್ ಜಿ ನೀಡಿದರೆ, ಮ್ಯಾಕ್ಸಿಮಮ್ ಕಟ್ ಅನ್ನು ಹುಡುಕಿ. ಆಪ್ಟಿಮೈಸೇಶನ್ ರೂಪಾಂತರವನ್ನು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಇದಕ್ಕೆ ವಿರುದ್ಧವಾದ ಸಮಸ್ಯೆಯೆಂದರೆ, ಕನಿಷ್ಠ ಕಡಿತವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಫೋರ್ಡ್-ಫುಲ್ಕರ್ಸನ್ ಅಲ್ಗಾರಿದಮ್ ಮೂಲಕ ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಪರಿಹರಿಸಬಹುದಾದ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಕ್ರಮಾವಳಿಗಳು ಬಹುಪದೀಯ-ಸಮಯ ಕ್ರಮಾವಳಿಗಳು ಗರಿಷ್ಠ-ಕಡಿತ ಸಮಸ್ಯೆಯು ಎನ್. ಪಿ.-ಕಠಿಣವಾಗಿರುವುದರಿಂದ, ಸಾಮಾನ್ಯ ರೇಖಾಚಿತ್ರಗಳಲ್ಲಿ ಗರಿಷ್ಠ-ಕಡಿತಕ್ಕೆ ಯಾವುದೇ ಬಹುಪದೀಯ-ಸಮಯ ಕ್ರಮಾವಳಿಗಳು ತಿಳಿದಿಲ್ಲ. ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳು ಆದಾಗ್ಯೂ, ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಲ್ಲಿ, ಮ್ಯಾಕ್ಸಿಮಮ್-ಕಟ್ ಸಮಸ್ಯೆಯು ಮಾರ್ಗ ಪರಿಶೀಲನಾ ಸಮಸ್ಯೆಗೆ ದ್ವಿಗುಣವಾಗಿದೆ (ಕನಿಷ್ಠ ಒಮ್ಮೆಯಾದರೂ ಗ್ರಾಫ್ನ ಪ್ರತಿ ಅಂಚಿಗೆ ಭೇಟಿ ನೀಡುವ ಚಿಕ್ಕ ಪ್ರವಾಸವನ್ನು ಕಂಡುಹಿಡಿಯುವ ಸಮಸ್ಯೆ), ಅಂದರೆ ಗ್ರಾಫ್ನ ಗರಿಷ್ಠ ಕಟ್-ಸೆಟ್ಗೆ ಸೇರದ ಅಂಚುಗಳು ಜಿ ಯ ಡ್ಯುಯಲ್ ಗ್ರಾಫ್ನ ಅತ್ಯುತ್ತಮ ತಪಾಸಣಾ ಪ್ರವಾಸದಲ್ಲಿ ದ್ವಿಗುಣಗೊಳ್ಳುವ ಅಂಚುಗಳ ಡ್ಯುಯಲ್ಗಳಾಗಿವೆ. ಆಪ್ಟಿಮಲ್ ಇನ್ಸ್ಪೆಕ್ಷನ್ ಪ್ರವಾಸವು ಸಮತಲವನ್ನು ಎರಡು ಉಪಗುಂಪುಗಳಾಗಿ ಬೇರ್ಪಡಿಸುವ ಸ್ವಯಂ-ಛೇದಿಸುವ ವಕ್ರರೇಖೆಯನ್ನು ರೂಪಿಸುತ್ತದೆ, ಇದು ವಕ್ರರೇಖೆಯ ಅಂಕುಡೊಂಕಾದ ಸಂಖ್ಯೆಯು ಸಮವಾಗಿರುವ ಬಿಂದುಗಳ ಉಪಗುಂಪು ಮತ್ತು ಅಂಕುಡೊಂಕಾದ ಸಂಖ್ಯೆಯು ಬೆಸವಾಗಿರುವ ಉಪಗುಂಪು; ಈ ಎರಡು ಉಪಗುಂಪುಗಳು ಅವುಗಳ ಡ್ಯುಯಲ್ಗಳು ಕಾಣಿಸಿಕೊಳ್ಳುವ ಎಲ್ಲಾ ಅಂಚುಗಳನ್ನು ಒಳಗೊಂಡಿರುವ ಕಟ್ ಅನ್ನು ರೂಪಿಸುತ್ತವೆ. ಮಾರ್ಗ ಪರಿಶೀಲನಾ ಸಮಸ್ಯೆಯನ್ನು ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಪರಿಹರಿಸಬಹುದು, ಮತ್ತು ಈ ದ್ವಂದ್ವತೆಯು ಪ್ಲ್ಯಾನರ್ ಗ್ರಾಫ್ಗಳಿಗೆ ಬಹುಪದೀಯ ಸಮಯದಲ್ಲಿ ಗರಿಷ್ಠ ಕಡಿತ ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಗರಿಷ್ಠ-ವಿಭಜನೆಯ ಸಮಸ್ಯೆಯನ್ನು ಎನ್. ಪಿ.-ಹಾರ್ಡ್ ಎಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳು ಗರಿಷ್ಠ-ಕಡಿತ ಸಮಸ್ಯೆಯು ಎಪಿಎಕ್ಸ್-ಕಠಿಣವಾಗಿದೆ, ಅಂದರೆ ಪಿ = ಎನ್ಪಿ ಹೊರತು, ಅದಕ್ಕೆ ಸೂಕ್ತವಾದ ಪರಿಹಾರಕ್ಕೆ ಅನಿಯಂತ್ರಿತವಾಗಿ ಹತ್ತಿರವಿರುವ ಯಾವುದೇ ಬಹುಪದ-ಸಮಯ ಅಂದಾಜು ಯೋಜನೆ (ಪಿಟಿಎಎಸ್) ಇಲ್ಲ. ಹೀಗಾಗಿ, ತಿಳಿದಿರುವ ಪ್ರತಿಯೊಂದು ಬಹುಪದ-ಸಮಯದ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಒಂದಕ್ಕಿಂತ ಕಡಿಮೆ ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಸಾಧಿಸುತ್ತದೆ. ಸರಳವಾದ ಯಾದೃಚ್ಛಿಕವಾದ 0.5-approximation ಕ್ರಮಾವಳಿ ಇದೆಃ ಪ್ರತಿ ಶೃಂಗಕ್ಕೂ ಒಂದು ನಾಣ್ಯವನ್ನು ತಿರುಗಿಸಿ, ಅದನ್ನು ಯಾವ ಭಾಗಕ್ಕೆ ನಿಯೋಜಿಸಬೇಕೆಂದು ನಿರ್ಧರಿಸಿ. ನಿರೀಕ್ಷೆಯಲ್ಲಿ, ಅಂಚುಗಳ ಅರ್ಧದಷ್ಟು ಕತ್ತರಿಸಿದ ಅಂಚುಗಳಾಗಿವೆ. ಷರತ್ತುಬದ್ಧ ಸಂಭವನೀಯತೆಗಳ ವಿಧಾನದೊಂದಿಗೆ ಈ ಅಲ್ಗಾರಿದಮ್ ಅನ್ನು ಬೇರ್ಪಡಿಸಬಹುದು; ಆದ್ದರಿಂದ ಸರಳ ನಿರ್ಣಾಯಕ ಬಹುಪದ-ಸಮಯ 0.5-approximation ಅಲ್ಗಾರಿದಮ್ ಸಹ ಇದೆ. ಅಂತಹ ಒಂದು ಅಲ್ಗಾರಿದಮ್ ನೀಡಲಾದ ಗ್ರಾಫ್ನ ಶೃಂಗಗಳ ಅನಿಯಂತ್ರಿತ ವಿಭಜನೆಯೊಂದಿಗೆ ಪ್ರಾರಂಭವಾಗುತ್ತದೆ ಮತ್ತು ವಿಭಜನೆಯ ಒಂದು ಬದಿಯಿಂದ ಇನ್ನೊಂದು ಬದಿಗೆ ಒಂದು ಸಮಯದಲ್ಲಿ ಒಂದು ಶೃಂಗವನ್ನು ಪದೇ ಪದೇ ಚಲಿಸುತ್ತದೆ, ಈ ರೀತಿಯ ಯಾವುದೇ ಸುಧಾರಣೆಗಳನ್ನು ಮಾಡುವವರೆಗೆ ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಪರಿಹಾರವನ್ನು ಸುಧಾರಿಸುತ್ತದೆ. ಪುನರಾವರ್ತನೆಗಳ ಸಂಖ್ಯೆಯು ಗರಿಷ್ಠವಾಗಿದೆ ಏಕೆಂದರೆ ಅಲ್ಗಾರಿದಮ್ ಪ್ರತಿ ಹಂತದಲ್ಲೂ ಕನಿಷ್ಠ ಒಂದು ತುದಿಯಿಂದ ಕಟ್ ಅನ್ನು ಸುಧಾರಿಸುತ್ತದೆ. ಅಲ್ಗಾರಿದಮ್ ಕೊನೆಗೊಂಡಾಗ, ಪ್ರತಿ ಶೃಂಗಕ್ಕೆ ಸಂಭವಿಸುವ ಅಂಚುಗಳ ಕನಿಷ್ಠ ಅರ್ಧದಷ್ಟು ಭಾಗವು ಕಟ್ಗೆ ಸೇರುತ್ತದೆ, ಇಲ್ಲದಿದ್ದರೆ ಶೃಂಗವನ್ನು ಚಲಿಸುವುದರಿಂದ ಕಟ್ ಅನ್ನು ಸುಧಾರಿಸುತ್ತದೆ. ಆದ್ದರಿಂದ, ಕಟ್ ಕನಿಷ್ಠ ಅಂಚುಗಳನ್ನು ಒಳಗೊಂಡಿದೆ. ಮ್ಯಾಕ್ಸ್-ಕಟ್ಗಾಗಿ ಬಹುಪದ-ಸಮಯದ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ ಅತ್ಯಂತ ಪ್ರಸಿದ್ಧವಾದ ಅಂದಾಜು ಅನುಪಾತದೊಂದಿಗೆ ಗೋಯೆಮನ್ಸ್ ಮತ್ತು ವಿಲಿಯಮ್ಸನ್ ಅವರು ಸೆಮಿಡಿಫೈನೈಟ್ ಪ್ರೋಗ್ರಾಮಿಂಗ್ ಮತ್ತು ಯಾದೃಚ್ಛಿಕ ರೌಂಡಿಂಗ್ ಅನ್ನು ಬಳಸುವ ಒಂದು ವಿಧಾನವಾಗಿದ್ದು, ಇದು ಅಂದಾಜು ಅನುಪಾತವನ್ನು ಸಾಧಿಸುತ್ತದೆ, ಅಲ್ಲಿ ಅನನ್ಯ ಆಟದ ಊಹೆಯು ನಿಜವಾಗಿದ್ದರೆ, ಇದು ಗರಿಷ್ಠ ಕಡಿತಕ್ಕೆ ಸಾಧ್ಯವಾದಷ್ಟು ಉತ್ತಮ ಅಂದಾಜು ಅನುಪಾತವಾಗಿದೆ. ಅಂತಹ ಸಾಬೀತಾಗದ ಊಹೆಗಳಿಲ್ಲದೆ, ಅದಕ್ಕಿಂತ ಉತ್ತಮವಾದ ಅಂದಾಜು ಅನುಪಾತದೊಂದಿಗೆ ಗರಿಷ್ಠ-ಕಡಿತ ಮೌಲ್ಯವನ್ನು ಅಂದಾಜು ಮಾಡುವುದು ಎನ್ಪಿ-ಹಾರ್ಡ್ ಎಂದು ಸಾಬೀತಾಗಿದೆ. ಇದರಲ್ಲಿ ಮುಕ್ತ-ಮೂಲ ಅನುಷ್ಠಾನವನ್ನು ಒಳಗೊಂಡಂತೆ ಈ ಸಮಸ್ಯೆಯ 10 ಶೋಧನೆಗಳ ವಿಸ್ತೃತ ವಿಶ್ಲೇಷಣೆ ಇದೆ. ನಿಯತಾಂಕಗಳ ಕ್ರಮಾವಳಿಗಳು ಮತ್ತು ಕರ್ನಲೈಸೇಶನ್ ಕನಿಷ್ಠ (ನಿಯತಾಂಕ) ಕೆ ಗಾತ್ರದ ಕಡಿತವನ್ನು ಕಂಡುಹಿಡಿಯುವ ಸಮಸ್ಯೆಯು ಸ್ಥಿರ-ನಿಯತಾಂಕದ ಟ್ರ್ಯಾಕ್ಟಬಲ್ (ಎಫ್ಪಿಟಿ) ಎಂದು ಸಾಬೀತುಪಡಿಸುವುದು ಕ್ಷುಲ್ಲಕವಾಗಿದ್ದರೂ, ಗ್ರಾಫ್ ಜಿ ಕನಿಷ್ಠ ಎಡ್ವರ್ಡ್ಸ್-ಎರ್ಡೋಸ್ ಲೋವರ್ ಬೌಂಡ್ (ಮೇಲಿನ ಕೆಳ ಮಿತಿಗಳನ್ನು ನೋಡಿ) ಪ್ಲಸ್ (ನಿಯತಾಂಕ) ಕೆ ಗಾತ್ರದ ಕಡಿತವನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ನಿರ್ಧರಿಸುವ ಸಮಸ್ಯೆಗೆ ಸ್ಥಿರ-ನಿಯತಾಂಕದ ಟ್ರ್ಯಾಕ್ಟಬಿಲಿಟಿಯನ್ನು ತೋರಿಸುವುದು ತುಂಬಾ ಕಷ್ಟ. ಸಮಸ್ಯೆಯನ್ನು ಸಮಯಕ್ಕೆ ಸರಿಯಾಗಿ ಪರಿಹರಿಸಬಹುದು ಎಂದು ಸಾಬೀತಾಯಿತು ಮತ್ತು ಗಾತ್ರದ ಕರ್ನಲ್ ಅನ್ನು ಒಪ್ಪಿಕೊಳ್ಳುತ್ತದೆ. ಕ್ರೌಸ್ಟನ್ ಮತ್ತು ಇತರರು. ಸ್ಥಿರ-ನಿಯತಾಂಕ ಟ್ರ್ಯಾಕ್ಟಬಿಲಿಟಿ ಫಲಿತಾಂಶವನ್ನು ಬ್ಯಾಲೆನ್ಸ್ಡ್ ಸಬ್ಗ್ರಾಫ್ ಪ್ರಾಬ್ಲಂಗೆ (ಬಿಎಸ್ಪಿ, ಮೇಲಿನ ಲೋವರ್ ಬೌಂಡರಿಗಳನ್ನು ನೋಡಿ) ವಿಸ್ತರಿಸಲಾಯಿತು ಮತ್ತು ಕರ್ನಲ್ ಗಾತ್ರವನ್ನು (ಬಿಎಸ್ಪಿಗೂ ಸಹ) ಸುಧಾರಿಸಿತು. ಎಟ್ಶೈಡ್ ಮತ್ತು ಮನಿಚ್ ಅವರು ಬಿಎಸ್ಪಿಗೆ ಸ್ಥಿರ-ನಿಯತಾಂಕ ಟ್ರ್ಯಾಕ್ಟಬಿಲಿಟಿ ಫಲಿತಾಂಶವನ್ನು ಮತ್ತು ಕರ್ನಲ್-ಗಾತ್ರದ ಫಲಿತಾಂಶವನ್ನು ಶೃಂಗಗಳಿಗೆ ಸುಧಾರಿಸಿದರು. ಅಪ್ಲಿಕೇಶನ್ಗಳು ಯಂತ್ರ ಕಲಿಕೆ ಅದರ ನೋಡ್ಗಳನ್ನು ವೈಶಿಷ್ಟ್ಯಗಳಾಗಿ ಮತ್ತು ಅದರ ಅಂಚುಗಳನ್ನು ದೂರಗಳಾಗಿ ಪರಿಗಣಿಸಿ, ಗರಿಷ್ಠ ಕಟ್ ಅಲ್ಗಾರಿದಮ್ ಗ್ರಾಫ್ ಅನ್ನು ಎರಡು ಚೆನ್ನಾಗಿ ಬೇರ್ಪಡಿಸಿದ ಉಪಗುಂಪುಗಳಾಗಿ ವಿಭಜಿಸುತ್ತದೆ. ಬೇರೆ ರೀತಿಯಲ್ಲಿ ಹೇಳುವುದಾದರೆ, ಬೈನರಿ ವರ್ಗೀಕರಣವನ್ನು ನಿರ್ವಹಿಸಲು ಇದನ್ನು ನೈಸರ್ಗಿಕವಾಗಿ ಅನ್ವಯಿಸಬಹುದು. ಹೆಚ್ಚು ಸಾಮಾನ್ಯವಾದ ವರ್ಗೀಕರಣ ಕ್ರಮಾವಳಿಗಳಿಗೆ ಹೋಲಿಸಿದರೆ, ಇದಕ್ಕೆ ವೈಶಿಷ್ಟ್ಯದ ಸ್ಥಳಾವಕಾಶದ ಅಗತ್ಯವಿಲ್ಲ, ಒಳಗಿನ ಅಂಶಗಳ ನಡುವಿನ ಅಂತರ ಮಾತ್ರ. ಸಂಖ್ಯಾಶಾಸ್ತ್ರೀಯ ಭೌತಶಾಸ್ತ್ರ ಮತ್ತು ಅವ್ಯವಸ್ಥಿತ ವ್ಯವಸ್ಥೆಗಳಲ್ಲಿ, ಮ್ಯಾಕ್ಸ್ ಕಟ್ ಸಮಸ್ಯೆಯು ಸ್ಪಿನ್ ಗ್ಲಾಸ್ ಮಾದರಿಯ ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಅನ್ನು ಕನಿಷ್ಠಗೊಳಿಸಲು ಸಮನಾಗಿರುತ್ತದೆ, ಇದು ಸರಳವಾಗಿ ಐಸಿಂಗ್ ಮಾದರಿಯಾಗಿದೆ. ಗ್ರಾಫ್ ಜಿ ಯಲ್ಲಿರುವ ಐಸಿಂಗ್ ಮಾದರಿಗೆ ಮತ್ತು ಹತ್ತಿರದ-ನೆರೆಯ ಪರಸ್ಪರ ಕ್ರಿಯೆಗಳಿಗೆ, ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಆಗಿದೆ ಇಲ್ಲಿ ಗ್ರಾಫ್ನ ಪ್ರತಿಯೊಂದು ಶೃಂಗವು ಸ್ಪಿನ್ ಮೌಲ್ಯವನ್ನು ತೆಗೆದುಕೊಳ್ಳುವ ಸ್ಪಿನ್ ಸೈಟ್ ಆಗಿದೆ ಎ ಸ್ಪಿನ್ ಕಾನ್ಫಿಗರೇಶನ್ ವಿಭಾಗಗಳನ್ನು ಎರಡು ಸೆಟ್ಗಳಾಗಿ ವಿಂಗಡಿಸಬಹುದು, ಸ್ಪಿನ್ ಅಪ್ ಮತ್ತು ಸ್ಪಿನ್ ಡೌನ್ ಇರುವವು. ನಂತರ ನಾವು ಹ್ಯಾಮಿಲ್ಟೋನಿಯನ್ ಅನ್ನು ಈ ಶಕ್ತಿಯನ್ನು ಕಡಿಮೆ ಮಾಡುವುದು ಮಿನಿ-ಕಟ್ ಸಮಸ್ಯೆಗೆ ಸಮನಾಗಿರುತ್ತದೆ ಅಥವಾ ಗ್ರಾಫ್ ತೂಕವನ್ನು ಗರಿಷ್ಠ-ಕಟ್ ಸಮಸ್ಯೆಯಾಗಿ ಹೊಂದಿಸುವ ಮೂಲಕ ಪುನಃ ಬರೆಯಬಹುದು. ಸರ್ಕ್ಯೂಟ್ ವಿನ್ಯಾಸ ಗರಿಷ್ಠ ಕಟ್ ಸಮಸ್ಯೆಯು ವಿಎಲ್ಎಸ್ಐ ವಿನ್ಯಾಸದಲ್ಲಿ ಅನ್ವಯಗಳನ್ನು ಹೊಂದಿದೆ. ಕನಿಷ್ಠ ಕಟ್ ಕನಿಷ್ಠ ಕೆ-ಕಟ್ ಆಡ್ ಸೈಕಲ್ ಟ್ರಾನ್ಸ್ವರ್ಸಲ್ ಅನ್ನು ಸಹ ನೋಡಿ, ಇದು ಅತಿದೊಡ್ಡ ಉಭಯಪಕ್ಷೀಯ ಪ್ರೇರಿತ ಉಪಗ್ರಾಫ್ ಅನ್ಫ್ರೆಂಡ್ಲಿ ವಿಭಾಗವನ್ನು ಕೇಳುವುದಕ್ಕೆ ಸಮಾನವಾಗಿದೆ, ಇದು ಅನಂತ ಗ್ರಾಫ್ಗಳ ಟಿಪ್ಪಣಿಗಳ ಉಲ್ಲೇಖಗಳಿಗೆ ಸಂಬಂಧಿಸಿದ ಪರಿಕಲ್ಪನೆಯಾಗಿದೆ. .. ಗರಿಷ್ಠ ಕಡಿತ (ಆಪ್ಟಿಮೈಸೇಶನ್ ಆವೃತ್ತಿ) ಎಂಬುದು ಅನುಬಂಧ ಬಿ (ಪುಟ 399) ನಲ್ಲಿರುವ ಎನ್. ಡಿ. 14 ಸಮಸ್ಯೆಯಾಗಿದೆ. .. .. .. .. .. .. .. .. .. ಗರಿಷ್ಠ ಕಡಿತ (ನಿರ್ಧಾರದ ಆವೃತ್ತಿ) ಎಂಬುದು ಅನುಬಂಧ ಎ2.2ರಲ್ಲಿರುವ ಎನ್. ಡಿ. 16 ಸಮಸ್ಯೆಯಾಗಿದೆ. ಅಪೆಂಡಿಕ್ಸ್ ಎ1.2ರಲ್ಲಿರುವ ಜಿಟಿ25 ಸಮಸ್ಯೆಯು ಗರಿಷ್ಠ ಉಭಯಪಕ್ಷೀಯ ಉಪಗ್ರಫ್ (ನಿರ್ಧಾರದ ಆವೃತ್ತಿ) ಆಗಿದೆ. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ಬಾಹ್ಯ ಕೊಂಡಿಗಳು ಪಿಯರ್ಲುಯಿಗಿ ಕ್ರೆಸೆಂಜಿ, ವಿಗ್ಗೊ ಕಾನ್, ಮ್ಯಾಗ್ನಸ್ ಹಾಲ್ಡಾರ್ಸನ್, ಮಾರೆಕ್ ಕಾರ್ಪಿನ್ಸ್ಕಿ, ಗೆರ್ಹಾರ್ಡ್ ವೋಯಿಂಗರ್ (2000), "ಮ್ಯಾಕ್ಸಿಮಮ್ ಕಟ್", "ಎ ಕಾಂಪೆಂಡಿಯಂ ಆಫ್ ಎನ್ಪಿ ಆಪ್ಟಿಮೈಸೇಶನ್ ಪ್ರಾಬ್ಲಮ್ಸ್" ನಲ್ಲಿ. ಆಂಡ್ರಿಯಾ ಕ್ಯಾಸಿನಿ, ನಿಕೋಲಾ ರೆಬಾಗ್ಲಿಯಾಟಿ (2012), "ಎ ಪೈಥಾನ್ ಲೈಬ್ರರಿ ಫಾರ್ ಸೊಲ್ವಿಂಗ್ ಮ್ಯಾಕ್ಸ್ ಕಟ್" ಗ್ರಾಫ್ ಥಿಯರಿ ಆಬ್ಜೆಕ್ಟ್ಸ್ ಕಾಂಬಿನೇಟೋರಿಯಲ್ ಆಪ್ಟಿಮೈಸೇಶನ್ ಎನ್ಪಿ-ಕಂಪ್ಲೀಟ್ ಸಮಸ್ಯೆಗಳು ಗ್ರಾಫ್ ಥಿಯರಿಯಲ್ಲಿ ಕಂಪ್ಯೂಟೇಶನಲ್ ಸಮಸ್ಯೆಗಳು