Domination analysis
1997ರಲ್ಲಿ ಗ್ಲೋವರ್ ಮತ್ತು ಪುನ್ನೆನ್ ಪರಿಚಯಿಸಿದ ಅಂದಾಜು ಅಲ್ಗಾರಿದಮ್ನ ಪ್ರಾಬಲ್ಯದ ವಿಶ್ಲೇಷಣೆಯು ಅದರ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ಅಂದಾಜು ಮಾಡುವ ಒಂದು ಮಾರ್ಗವಾಗಿದೆ. ಲೆಕ್ಕ ಹಾಕಿದ ಪರಿಹಾರದ ಸಂಖ್ಯಾತ್ಮಕ ಗುಣಮಟ್ಟವನ್ನು ಅತ್ಯುತ್ತಮ ಪರಿಹಾರದೊಂದಿಗೆ ಹೋಲಿಸುವ ಶಾಸ್ತ್ರೀಯ ಅಂದಾಜು ಅನುಪಾತದ ವಿಶ್ಲೇಷಣೆಯಂತಲ್ಲದೆ, ಪ್ರಾಬಲ್ಯದ ವಿಶ್ಲೇಷಣೆಯು ಎಲ್ಲಾ ಸಂಭವನೀಯ ಪರಿಹಾರಗಳ ವಿಂಗಡಿಸಲಾದ ಕ್ರಮದಲ್ಲಿ ಲೆಕ್ಕ ಹಾಕಿದ ಪರಿಹಾರದ ಶ್ರೇಣಿಯನ್ನು ಪರಿಶೀಲಿಸುವುದನ್ನು ಒಳಗೊಂಡಿರುತ್ತದೆ. ಈ ವಿಶ್ಲೇಷಣೆಯ ಶೈಲಿಯಲ್ಲಿ, ಅಲ್ಗಾರಿದಮ್ನ ಔಟ್ಪುಟ್ ಅತ್ಯುತ್ತಮವಾಗಿರುವ ಸಮಸ್ಯೆಗೆ ಕೆ ವಿಭಿನ್ನ ಪರಿಹಾರಗಳ ಉಪವಿಭಾಗವಿದ್ದರೆ, ಅಲ್ಗಾರಿದಮ್ ಪ್ರಾಬಲ್ಯ ಸಂಖ್ಯೆ ಅಥವಾ ಪ್ರಾಬಲ್ಯ ಸಂಖ್ಯೆ ಕೆ ಅನ್ನು ಹೊಂದಿದೆ ಎಂದು ಹೇಳಲಾಗುತ್ತದೆ. ಪ್ರಾಬಲ್ಯದ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಪ್ರಾಬಲ್ಯದ ಅನುಪಾತವನ್ನು ಬಳಸಿಕೊಂಡು ವ್ಯಕ್ತಪಡಿಸಬಹುದು, ಇದು ನೀಡಲಾದ ಪರಿಹಾರಕ್ಕಿಂತ ಉತ್ತಮವಲ್ಲದ ಪರಿಹಾರ ಸ್ಥಳದ ಭಾಗವಾಗಿದೆ; ಈ ಸಂಖ್ಯೆಯು ಯಾವಾಗಲೂ ಮಧ್ಯಂತರದೊಳಗೆ ಇರುತ್ತದೆ [0,1], ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಗಳು ಉತ್ತಮ ಪರಿಹಾರಗಳನ್ನು ಸೂಚಿಸುತ್ತವೆ. ಸಂಭಾವ್ಯ ಪರಿಹಾರಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆ ತಿಳಿದಿರುವ ಮತ್ತು ನಿಖರವಾದ ಪರಿಹಾರವು ಕಷ್ಟಕರವಾದ ಸಮಸ್ಯೆಗಳಿಗೆ ಪ್ರಾಬಲ್ಯದ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಅನ್ವಯಿಸಲಾಗುತ್ತದೆ. ಉದಾಹರಣೆಗೆ, ಟ್ರಾವೆಲಿಂಗ್ ಸೇಲ್ಸ್ಮ್ಯಾನ್ ಸಮಸ್ಯೆಯಲ್ಲಿ, (ಎನ್-1) ಇವೆ! n ನಗರಗಳೊಂದಿಗಿನ ಸಮಸ್ಯೆಯ ಉದಾಹರಣೆಗೆ ಸಂಭವನೀಯ ಪರಿಹಾರಗಳು. ಒಂದು ಅಲ್ಗಾರಿದಮ್ ಪ್ರಾಬಲ್ಯದ ಸಂಖ್ಯೆಯನ್ನು (n-1)! ಗೆ ಹತ್ತಿರದಲ್ಲಿದೆ ಎಂದು ತೋರಿಸಬಹುದಾದರೆ, ಅಥವಾ ಪ್ರಾಬಲ್ಯದ ಅನುಪಾತವನ್ನು 1 ಕ್ಕೆ ಹತ್ತಿರದಲ್ಲಿದೆ ಎಂದು ತೋರಿಸಬಹುದಾದರೆ, ಅದನ್ನು ಕಡಿಮೆ ಪ್ರಾಬಲ್ಯದ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರುವ ಅಲ್ಗಾರಿದಮ್ಗೆ ಆದ್ಯತೆ ಎಂದು ತೆಗೆದುಕೊಳ್ಳಬಹುದು. ಟ್ರಾವೆಲಿಂಗ್ ಸೇಲ್ಸ್ಮ್ಯಾನ್ ಸಮಸ್ಯೆಯಲ್ಲಿರುವಂತೆ, ಸಮಸ್ಯೆಯ ಪರಿಹಾರ ಸ್ಥಳದ ಯಾದೃಚ್ಛಿಕ ಮಾದರಿಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಕಂಡುಹಿಡಿಯಲು ಸಾಧ್ಯವಾದರೆ, ಹೆಚ್ಚಿನ ಸಂಭವನೀಯತೆಯೊಂದಿಗೆ ಹೆಚ್ಚಿನ ಪ್ರಾಬಲ್ಯದ ಅನುಪಾತವನ್ನು ಹೊಂದಿರುವ ಪರಿಹಾರವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಯಾದೃಚ್ಛಿಕ ಅಲ್ಗಾರಿದಮ್ಗೆ ಸರಳವಾಗಿದೆಃ ಸರಳವಾಗಿ ಮಾದರಿಗಳ ಗುಂಪನ್ನು ನಿರ್ಮಿಸಿ ಮತ್ತು ಅವುಗಳಲ್ಲಿ ಅತ್ಯುತ್ತಮ ಪರಿಹಾರವನ್ನು ಆಯ್ಕೆ ಮಾಡಿ. (ನೋಡಿ, ಉದಾಹರಣೆಗೆ, ಓರ್ಲಿನ್ ಮತ್ತು ಶರ್ಮಾ.) ಇಲ್ಲಿ ವಿವರಿಸಲಾದ ಪ್ರಾಬಲ್ಯದ ಸಂಖ್ಯೆಯನ್ನು ಗ್ರಾಫ್ನ ಪ್ರಾಬಲ್ಯದ ಸಂಖ್ಯೆಯೊಂದಿಗೆ ಗೊಂದಲಗೊಳಿಸಬಾರದು, ಇದು ಗ್ರಾಫ್ನ ಅತ್ಯಂತ ಚಿಕ್ಕ ಪ್ರಾಬಲ್ಯದ ಗುಂಪಿನಲ್ಲಿನ ಶೃಂಗಗಳ ಸಂಖ್ಯೆಯನ್ನು ಸೂಚಿಸುತ್ತದೆ. ಇತ್ತೀಚೆಗೆ, ಹ್ಯೂರಿಸ್ಟಿಕ್ಸ್ನ ಕಾರ್ಯಕ್ಷಮತೆಯನ್ನು ನಿರ್ಣಯಿಸಲು ಪ್ರಾಬಲ್ಯದ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಅನ್ವಯಿಸಲಾಗಿರುವ ಲೇಖನಗಳ ಸಂಖ್ಯೆ ಹೆಚ್ಚುತ್ತಿದೆ. ಈ ರೀತಿಯ ವಿಶ್ಲೇಷಣೆಯನ್ನು ಶಾಸ್ತ್ರೀಯ ಅಂದಾಜು ಅನುಪಾತ ವಿಶ್ಲೇಷಣೆಯ ಸಂಪ್ರದಾಯದೊಂದಿಗೆ ಸ್ಪರ್ಧಿಸುವಂತೆ ಕಾಣಬಹುದು. ಈ ಎರಡು ಕ್ರಮಗಳನ್ನು ಪೂರಕವೆಂದು ಪರಿಗಣಿಸಬಹುದು. ತಿಳಿದಿರುವ ಫಲಿತಾಂಶಗಳು ಈ ವಿಭಾಗವು ತಿಳಿದಿರುವ ಫಲಿತಾಂಶಗಳ ತಾಂತ್ರಿಕ ಸಮೀಕ್ಷೆಯನ್ನು ಒಳಗೊಂಡಿದೆ. ವೆರ್ಟೆಕ್ಸ್ ಕವರ್ ಅಸಮರ್ಪಕವಾಗಿದೆ. ε> 0 ಆಗಿರಲಿ. ಪಿ = ಎನ್ಪಿ ಹೊರತು, ವೆರ್ಟೆಕ್ಸ್ ಕವರ್ಗೆ ಯಾವುದೇ ಬಹುಪದ ಅಲ್ಗಾರಿದಮ್ ಇಲ್ಲ, ಅಂದರೆ ಅದರ ಪ್ರಾಬಲ್ಯ ಸಂಖ್ಯೆ 3 ((ಎನ್-ಎನ್)/3) ಗಿಂತ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ನಾಪ್ಸ್ಯಾಕ್ ಅಸಮರ್ಪಕತೆ. ε> 0 ಆಗಿರಲಿ. ಪಿ = ಎನ್ಪಿ ಹೊರತು, ನಾಪ್ಸ್ಯಾಕ್ಗೆ ಯಾವುದೇ ಬಹುಪದ ಕ್ರಮಾವಳಿಗಳಿಲ್ಲ, ಅಂದರೆ ಅದರ ಪ್ರಾಬಲ್ಯದ ಸಂಖ್ಯೆಯು 2ನೇ (ಎನ್-ಎನ್) ಗಿಂತ ಹೆಚ್ಚಾಗಿರುತ್ತದೆ. ಗರಿಷ್ಠ ತೃಪ್ತಿಯ ಟಿ. ಎಸ್. ಪಿ. ಉಲ್ಲೇಖಗಳು ಅಂದಾಜು ಕ್ರಮಾವಳಿಗಳು