Randomized rounding
કોમ્પ્યુટર સાયન્સ અને ઓપરેશન્સ રિસર્ચમાં, રેન્ડમાઇઝ્ડ રાઉન્ડિંગ એ અંદાજિત અલ્ગોરિધમ્સની રચના અને વિશ્લેષણ માટે વ્યાપકપણે ઉપયોગમાં લેવાતો અભિગમ છે. ઘણી સંયુક્ત ઓપ્ટિમાઇઝેશન સમસ્યાઓ બરાબર (ઓપ્ટિમાલિટી) ઉકેલવા માટે કોમ્પ્યુટેશનલ રીતે અવ્યવહારુ છે. આવી સમસ્યાઓ માટે, રેન્ડમાઇઝ્ડ રાઉન્ડિંગનો ઉપયોગ ઝડપી (બહુપદી સમય) અંદાજ અલ્ગોરિધમ્સ ડિઝાઇન કરવા માટે થઈ શકે છે-એટલે કે, એલ્ગોરિધમ્સ કે જે કોઈપણ ઇનપુટને ધ્યાનમાં રાખીને લગભગ શ્રેષ્ઠ ઉકેલ પરત કરવાની ખાતરી આપે છે. રેન્ડમાઇઝ્ડ રાઉન્ડિંગનો મૂળભૂત વિચાર એ છે કે સમસ્યામાં છૂટછાટના શ્રેષ્ઠ ઉકેલને મૂળ સમસ્યાના લગભગ શ્રેષ્ઠ ઉકેલમાં રૂપાંતરિત કરવો. પરિણામી અલ્ગોરિધમનું સામાન્ય રીતે સંભવિત પદ્ધતિનો ઉપયોગ કરીને વિશ્લેષણ કરવામાં આવે છે. ઝાંખી મૂળભૂત અભિગમના ત્રણ તબક્કાઓ છેઃ પૂર્ણાંક રેખીય કાર્યક્રમ (આઇએલપી) તરીકે ઉકેલવા માટેની સમસ્યાની રચના કરો. આઇ. એલ. પી. ના રેખીય પ્રોગ્રામિંગ છૂટછાટ (એલ. પી.) માટે શ્રેષ્ઠ અપૂર્ણાંક ઉકેલની ગણતરી કરો. એલ. પી. ના અપૂર્ણાંક ઉકેલને આઇ. એલ. પી. ના પૂર્ણાંક ઉકેલમાં ગોળાકાર કરો. (જોકે આ અભિગમ સામાન્ય રીતે રેખીય કાર્યક્રમો સાથે લાગુ કરવામાં આવે છે, કેટલીકવાર અન્ય પ્રકારની છૂટછાટનો ઉપયોગ કરવામાં આવે છે. ઉદાહરણ તરીકે, ગોમેન્સ અને વિલિયમસનનું સેમિડિફાઇનાઇટ પ્રોગ્રામિંગ-આધારિત મેક્સ-કટ એપ્રોક્સીમેશન અલ્ગોરિધમ જુઓ.) પ્રથમ તબક્કામાં, પડકાર એ છે કે યોગ્ય પૂર્ણાંક રેખીય પ્રોગ્રામ પસંદ કરવો. રેખીય પ્રોગ્રામિંગ સાથે પરિચિતતા, ખાસ કરીને રેખીય કાર્યક્રમો અને પૂર્ણાંક રેખીય કાર્યક્રમોનો ઉપયોગ કરીને મોડેલિંગ, જરૂરી છે. ઘણી સમસ્યાઓ માટે, એક કુદરતી પૂર્ણાંક રેખીય પ્રોગ્રામ છે જે સારી રીતે કામ કરે છે, જેમ કે નીચે સેટ કવર ઉદાહરણમાં. (પૂર્ણાંક રેખીય પ્રોગ્રામમાં એક નાનું ઇન્ટિગ્રાલિટી ગેપ હોવું જોઈએ; ખરેખર રેન્ડમાઇઝ્ડ રાઉન્ડિંગનો ઉપયોગ ઘણીવાર ઇન્ટિગ્રાલિટી ગેપ પર સીમા સાબિત કરવા માટે થાય છે. બીજા તબક્કામાં, શ્રેષ્ઠ અપૂર્ણાંક ઉકેલની ગણતરી સામાન્ય રીતે કોઈપણ પ્રમાણભૂત રેખીય પ્રોગ્રામિંગ અલ્ગોરિધમનો ઉપયોગ કરીને બહુપદી સમયમાં કરી શકાય છે. ત્રીજા તબક્કામાં, અપૂર્ણાંક ઉકેલને પૂર્ણાંક ઉકેલમાં રૂપાંતરિત કરવો આવશ્યક છે (અને આમ મૂળ સમસ્યાનું સમાધાન). આને અપૂર્ણાંક ઉકેલને ગોળાકાર કરવાનું કહેવામાં આવે છે. પરિણામી પૂર્ણાંક ઉકેલની કિંમત (સાબિત રીતે) અપૂર્ણાંક ઉકેલની કિંમત કરતાં ઘણી વધારે ન હોવી જોઈએ. આ સુનિશ્ચિત કરશે કે પૂર્ણાંક ઉકેલની કિંમત શ્રેષ્ઠ પૂર્ણાંક ઉકેલની કિંમત કરતાં ઘણી વધારે નથી. ત્રીજું પગલું (ગોળાકાર) કરવા માટે ઉપયોગમાં લેવાતી મુખ્ય તકનીક રેન્ડમાઇઝેશનનો ઉપયોગ કરવાની છે, અને પછી ગોળાકારને કારણે ખર્ચમાં થયેલા વધારાને બંધાવવા માટે સંભવિત દલીલોનો ઉપયોગ કરવાની છે (સંયોજનમાંથી સંભવિત પદ્ધતિને અનુસરીને). તેમાં, સંભવિત દલીલો ઇચ્છિત ગુણધર્મો સાથે સ્વતંત્ર માળખાના અસ્તિત્વને દર્શાવવા માટે વપરાય છે. આ સંદર્ભમાં, નીચે દર્શાવવા માટે આવી દલીલો વપરાય છેઃ એલ. પી. ના કોઈપણ અપૂર્ણાંક ઉકેલને જોતાં, હકારાત્મક સંભાવના સાથે રેન્ડમાઇઝ્ડ રાઉન્ડિંગ પ્રક્રિયા એક પૂર્ણાંક ઉકેલ ઉત્પન્ન કરે છે જે કેટલાક ઇચ્છિત માપદંડ અનુસાર અંદાજિત થાય છે. છેવટે, ત્રીજા પગલાને ગણતરીની રીતે કાર્યક્ષમ બનાવવા માટે, એક કાં તો દર્શાવે છે કે તે ઉચ્ચ સંભાવના સાથે અંદાજિત છે (જેથી પગલું અવ્યવસ્થિત રહી શકે છે) અથવા એક ગોળાકાર પગલાને અવ્યવસ્થિત કરે છે, સામાન્ય રીતે શરતી સંભાવનાઓની પદ્ધતિનો ઉપયોગ કરીને. પછીની પદ્ધતિ રેન્ડમાઇઝ્ડ ગોળાકાર પ્રક્રિયાને એક કાર્યક્ષમ નિર્ધારક પ્રક્રિયામાં રૂપાંતરિત કરે છે જે સારા પરિણામ સુધી પહોંચવાની ખાતરી આપે છે. ઉદાહરણ તરીકેઃ સેટ કવર પ્રોબ્લેમ નીચેનું ઉદાહરણ સમજાવે છે કે સેટ કવર પ્રોબ્લેમ માટે અંદાજિત અલ્ગોરિધમ ડિઝાઇન કરવા માટે રેન્ડમાઇઝ્ડ રાઉન્ડિંગનો ઉપયોગ કેવી રીતે કરી શકાય છે. બ્રહ્માંડ પર સેટ કવરના કોઈપણ ઉદાહરણને ઠીક કરો. અપૂર્ણાંક ઉકેલની ગણતરી પગલું 1 માટે, ચાલો આ ઉદાહરણ માટે સેટ કવર માટે આઇપી પ્રમાણભૂત પૂર્ણાંક રેખીય પ્રોગ્રામ છે. પગલું 2 માટે, ચાલો એલ. પી. એ આઇ. પી. ની રેખીય પ્રોગ્રામિંગ છૂટછાટ છે, અને કોઈપણ પ્રમાણભૂત રેખીય પ્રોગ્રામિંગ અલ્ગોરિધમનો ઉપયોગ કરીને એલ. પી. માટે શ્રેષ્ઠ ઉકેલની ગણતરી કરો. આ ઇનપુટ કદમાં બહુપદીમાં સમય લે છે. એલ. પી. માટે શક્ય ઉકેલો એ વેક્ટર છે જે દરેક સમૂહને બિન-નકારાત્મક વજન આપે છે, જેમ કે, દરેક તત્વ માટે, આવરી લે છે-- સમાવિષ્ટ સમૂહને સોંપેલ કુલ વજન ઓછામાં ઓછું 1 છે, એટલે કે, શ્રેષ્ઠ ઉકેલ એ શક્ય ઉકેલ છે જેની કિંમત શક્ય તેટલી ઓછી છે. નોંધ લો કે માટે કોઈપણ સેટ કવર શક્ય ઉકેલ આપે છે (જ્યાં માટે, અન્યથા). આનો ખર્ચ, એટલે કે, બીજા શબ્દોમાં કહીએ તો, રેખીય પ્રોગ્રામ એલ. પી. એ આપેલ સેટ-કવર સમસ્યામાં છૂટછાટ છે. એલ. પી. માટે શક્ય ઉકેલોમાં લઘુતમ ખર્ચ હોવાથી, મહત્તમ સેટ કવરની કિંમત પર તેની કિંમત ઓછી મર્યાદા હોય છે. રેન્ડમાઇઝ્ડ રાઉન્ડિંગ પગલું પગલું 3 માં, આપણે લઘુતમ-કિંમતના અપૂર્ણાંક સેટ કવરને શક્ય પૂર્ણાંક ઉકેલ (સાચા સેટ કવરને અનુરૂપ) માં રૂપાંતરિત કરવું જોઈએ. ગોળાકાર પગલાથી, હકારાત્મક સંભાવના સાથે, કિંમતના નાના પરિબળમાં કિંમત હોવી જોઈએ. પછી (કારણ કે કિંમત શ્રેષ્ઠ સેટ કવરની કિંમત પર ઓછી મર્યાદા છે), કિંમત શ્રેષ્ઠ ખર્ચના નાના પરિબળમાં હશે. પ્રારંભિક બિંદુ તરીકે, સૌથી કુદરતી ગોળાકાર યોજનાને ધ્યાનમાં લોઃ બદલામાં દરેક સમૂહ માટે, સંભાવના સાથે લો, અન્યથા લો. આ ગોળાકાર યોજના સાથે, પસંદ કરેલા સમૂહોની અપેક્ષિત કિંમત મહત્તમ છે, અપૂર્ણાંક આવરણની કિંમત. આ સારું છે. કમનસીબે કવરેજ સારું નથી. જ્યારે ચલ નાના હોય છે, ત્યારે કોઈ તત્વ આવરી લેવામાં ન આવે તેની સંભાવના લગભગ હોય છે. ઉચ્ચ સંભાવના સાથે દરેક તત્વને આવરી લેવા માટે, પ્રમાણભૂત ગોળાકાર યોજના પ્રથમ યોગ્ય પરિબળ દ્વારા ગોળાકાર સંભાવનાઓને માપે છે. અહીં પ્રમાણભૂત ગોળાકાર યોજના છેઃ પરિમાણને ઠીક કરો. બદલામાં દરેક સમૂહ માટે, સંભાવના સાથે લો, અન્યથા લો. સંભાવનાઓને વધારીને અપેક્ષિત ખર્ચમાં વધારો થાય છે, પરંતુ તમામ ઘટકોનું કવરેજ સંભવિત બનાવે છે. વિચાર એ છે કે શક્ય તેટલું નાનું પસંદ કરવું જેથી તમામ ઘટકો બિન-શૂન્ય સંભાવના સાથે સાબિત થાય. અહીં વિગતવાર વિશ્લેષણ છે. લેમ્મા (ગોળાકાર યોજના માટે અંદાજિત ગેરંટી) ફિક્સ. હકારાત્મક સંભાવના સાથે, ગોળાકાર યોજના મહત્તમ ખર્ચનું એક સેટ કવર આપે છે (અને આમ મહત્તમ સેટ કવરની કિંમતનો ખર્ચ ગુણાકાર કરે છે). (નોંધઃ કાળજી સાથે ઘટાડી શકાય છે.) પુરાવો રેન્ડમ ગોળાકાર યોજનાના ઉત્પાદનમાં ઇચ્છિત ગુણધર્મો હોય છે જ્યાં સુધી નીચેની "ખરાબ" ઘટનાઓમાંથી કોઈ ન બનેઃ ઓળંગની કિંમત, અથવા કેટલાક ઘટકો માટે, આવરી લેવામાં નિષ્ફળ જાય છે. દરેકની અપેક્ષા સૌથી વધુ હોય છે. અપેક્ષાઓની રેખીયતા દ્વારા, અપેક્ષા સૌથી વધુ છે. આમ, માર્કોવની અસમાનતા દ્વારા, ઉપરની પ્રથમ ખરાબ ઘટનાની સંભાવના સૌથી વધુ છે. બાકીની ખરાબ ઘટનાઓ માટે (દરેક તત્વ માટે એક), નોંધ લો કે, કોઈપણ આપેલ તત્વ માટે, જે સંભાવના આવરી લેવામાં આવી નથી તે છે (આ અસમાનતાનો ઉપયોગ કરે છે, જે તેના માટે કડક છે.) આમ, દરેક તત્વ માટે, તત્વ આવરી લેવામાં ન આવે તેની સંભાવના તેના કરતા ઓછી છે. યુનિયન બાઉન્ડ દ્વારા, ખરાબ ઘટનાઓમાંની એક થવાની સંભાવના તેના કરતા ઓછી છે. આમ, હકારાત્મક સંભાવના સાથે કોઈ ખરાબ ઘટનાઓ નથી અને તે મહત્તમ ખર્ચનું એક સેટ કવર છે. શરતી સંભાવનાઓની પદ્ધતિનો ઉપયોગ કરીને ક્યુ. ઇ. ડી. ડીરાન્ડોમાઇઝેશન ઉપરોક્ત લેમ્મા ખર્ચના સેટ કવરનું અસ્તિત્વ દર્શાવે છે). આ સંદર્ભમાં આપણું લક્ષ્ય એક કાર્યક્ષમ અંદાજ અલ્ગોરિધમ છે, માત્ર અસ્તિત્વનો પુરાવો નથી, તેથી આપણે પૂર્ણ કર્યું નથી. એક અભિગમ થોડો વધારો કરવાનો હશે, પછી બતાવશો કે સફળતાની સંભાવના ઓછામાં ઓછી, કહો, 1/4 છે. આ ફેરફાર સાથે, રેન્ડમ ગોળાકાર પગલાને થોડા વખત પુનરાવર્તન કરવું એ ઉચ્ચ સંભાવના સાથે સફળ પરિણામ સુનિશ્ચિત કરવા માટે પૂરતું છે. તે અભિગમ અંદાજ ગુણોત્તરને નબળો પાડે છે. અમે આગળ એક અલગ અભિગમનું વર્ણન કરીએ છીએ જે એક નિર્ધારક અલ્ગોરિધમ આપે છે જે ઉપરના અસ્તિત્વના પુરાવાના અંદાજ ગુણોત્તર સાથે મેળ ખાવાની ખાતરી આપે છે. આ અભિગમને શરતી સંભાવનાઓની પદ્ધતિ કહેવામાં આવે છે. નિર્ધારક અલ્ગોરિધમ રેન્ડમાઇઝ્ડ ગોળાકાર યોજનાનું અનુકરણ કરે છેઃ તે દરેક સમૂહને બદલામાં ધ્યાનમાં લે છે અને પસંદ કરે છે. પરંતુ દરેક પસંદગીને અવ્યવસ્થિત રીતે તેના પર આધારિત કરવાને બદલે, તે પસંદગીને નિર્ણાયક બનાવે છે, જેથી નિષ્ફળતાની શરતી સંભાવનાને જાળવી શકાય, અત્યાર સુધીની પસંદગીઓને ધ્યાનમાં રાખીને, 1 થી નીચે. નિષ્ફળતાની શરતી સંભાવનાને સીમિત કરવી આપણે દરેક ચલને બદલામાં સેટ કરવામાં સક્ષમ થવા માંગીએ છીએ જેથી નિષ્ફળતાની શરતી સંભાવનાને 1 થી નીચે રાખી શકાય. આ કરવા માટે, આપણે નિષ્ફળતાની શરતી સંભાવના પર સારી મર્યાદાની જરૂર છે. મૂળ અસ્તિત્વના સાબિતીને સુધારીને બાઉન્ડ આવશે. તે પુરાવો સ્પષ્ટ રીતે નિષ્ફળતાની સંભાવનાને રેન્ડમ વેરિયેબલની અપેક્ષા દ્વારા મર્યાદિત કરે છે, જ્યાં અંતે ખુલ્લા રહેલા તત્વોનો સમૂહ છે. રેન્ડમ ચલ થોડો રહસ્યમય દેખાઈ શકે છે, પરંતુ તે વ્યવસ્થિત રીતે સંભવિત સાબિતીને પ્રતિબિંબિત કરે છે. પ્રથમ ખરાબ ઘટના (કિંમત ખૂબ વધારે છે) ની સંભાવનાને બંધાવવા માટે માર્કોવની અસમાનતાને લાગુ કરવાથી પ્રથમ શબ્દ આવે છે. જો કિંમત ખૂબ વધારે હોય તો તે ઓછામાં ઓછું 1 નું યોગદાન આપે છે. બીજી મુદત બીજા પ્રકારની ખરાબ ઘટનાઓની સંખ્યા (ખુલ્લા તત્વો) ની ગણતરી કરે છે. જો કોઈ તત્વ ખુલ્લું રહે તો તે ઓછામાં ઓછું 1 નું યોગદાન આપે છે. આમ, કોઈપણ પરિણામમાં જ્યાં 1 કરતા ઓછું હોય, ત્યાં તમામ તત્વોને આવરી લેવા જોઈએ અને લેમ્મામાંથી ઇચ્છિત મર્યાદાને પૂર્ણ કરતી કિંમત હોવી જોઈએ. ટૂંકમાં, જો ગોળાકાર પગલું નિષ્ફળ જાય, તો પછી. આ સૂચવે છે (માર્કોવની અસમાનતા દ્વારા) જે નિષ્ફળતાની સંભાવના પર ઉપલી મર્યાદા છે. નોંધ લો કે ઉપરની દલીલ લેમ્માના સાબિતીમાં પહેલેથી જ ગર્ભિત છે, જે ગણતરી દ્વારા પણ દર્શાવે છે. શરતી સંભાવનાઓની પદ્ધતિ લાગુ કરવા માટે, આપણે ગોળાકાર પગલું આગળ વધતાં નિષ્ફળતાની શરતી સંભાવનાને બંધાવવા માટે દલીલને વિસ્તૃત કરવાની જરૂર છે. સામાન્ય રીતે, આ વ્યવસ્થિત રીતે કરી શકાય છે, જો કે તે તકનીકી રીતે કંટાળાજનક હોઈ શકે છે. તો, નિષ્ફળતાની શરતી સંભાવના વિશે શું કારણ કે ગોળાકાર પગલું સમૂહોમાંથી પુનરાવર્તન કરે છે? કારણ કે કોઈપણ પરિણામમાં જ્યાં માર્કોવની અસમાનતા દ્વારા ગોળાકાર પગલું નિષ્ફળ જાય છે, ત્યાં નિષ્ફળતાની શરતી સંભાવના સૌથી વધુ શરતી અપેક્ષા છે. આગળ આપણે શરતી અપેક્ષાની ગણતરી કરીએ છીએ, જેમ આપણે મૂળ સાબિતીમાં બિનશરતી અપેક્ષાની ગણતરી કરી હતી. અમુક પુનરાવર્તનના અંતે ગોળાકાર પ્રક્રિયાની સ્થિતિનો વિચાર કરો. ચાલો અત્યાર સુધી ગણવામાં આવેલા સમૂહોને દર્શાવીએ (પ્રથમ સમૂહો). ચાલો (આંશિક રીતે સોંપાયેલ) વેક્ટરને દર્શાવીએ (તેથી તે માત્ર જો નક્કી કરવામાં આવે તો). દરેક સમૂહ માટે, ચાલો સંભાવના દર્શાવીએ જેની સાથે 1 પર સેટ કરવામાં આવશે. ચાલો હજુ સુધી આવરી ન લેવાયેલા તત્વોને સમાવીએ. પછી શરતી અપેક્ષા, અત્યાર સુધી કરવામાં આવેલી પસંદગીઓને ધ્યાનમાં રાખીને, એટલે કે, નોંધ આપવામાં આવે છે જે પુનરાવર્તન પછી જ નક્કી થાય છે. નિષ્ફળતાની શરતી સંભાવનાને 1થી નીચે રાખવી નિષ્ફળતાની શરતી સંભાવનાને 1થી નીચે રાખવા માટે, 1થી નીચેની શરતી અપેક્ષા રાખવા માટે પૂરતું છે. આ કરવા માટે, તે વધવાની શરતી અપેક્ષા રાખવા માટે પૂરતું છે. અલ્ગોરિધમ આ જ કરશે. તે (ક્યાં) સુનિશ્ચિત કરવા માટે તે દરેક પુનરાવર્તનમાં સુયોજિત થશે. છઠ્ઠા પુનરાવર્તનમાં, તે સુનિશ્ચિત કરવા માટે અલ્ગોરિધમ કેવી રીતે સેટ કરી શકાય? તે તારણ આપે છે કે તે સરળતાથી સેટ કરી શકે છે જેથી પરિણામી મૂલ્યને ઘટાડી શકાય. શા માટે તે જોવા માટે, પુનરાવર્તન શરૂ થાય તે સમયના બિંદુ પર ધ્યાન કેન્દ્રિત કરો. તે સમયે, નક્કી કરવામાં આવે છે, પરંતુ હજુ સુધી નક્કી કરવામાં આવ્યું નથી---તે પુનરાવર્તનમાં કેવી રીતે સેટ કરવામાં આવે છે તેના આધારે બે સંભવિત મૂલ્યો લઈ શકે છે. ચાલો તેનું મૂલ્ય દર્શાવીએ. ચાલો અને, અનુક્રમે 0 અથવા 1 પર સેટ કરેલ છે કે કેમ તેના આધારે બે સંભવિત મૂલ્યોને દર્શાવો. શરતી અપેક્ષા ની વ્યાખ્યા મુજબ, બે જથ્થાની ભારિત સરેરાશ હંમેશા તે બે જથ્થાની ઓછામાં ઓછી હોય છે, તેથી તે નીચે મુજબ છે. અલ્ગોરિધમ આ જ કરશે. વિગતવાર, આનો અર્થ શું છે? (અન્ય તમામ જથ્થાઓ નિશ્ચિત સાથે) ના વિધેય તરીકે ગણવામાં આવે છે તે એક રેખીય વિધેય છે, અને તે વિધેયમાં ગુણાંક છે આમ, જો આ અભિવ્યક્તિ હકારાત્મક હોય તો અલ્ગોરિધમ 0 પર સેટ થવું જોઈએ, અને અન્યથા 1. આ નીચેનું અલ્ગોરિધમ આપે છે. સેટ કવર ઇનપુટ માટે રેન્ડમાઇઝ્ડ-રાઉન્ડિંગ અલ્ગોરિધમઃ સેટ સિસ્ટમ, યુનિવર્સ, કોસ્ટ વેક્ટર આઉટપુટઃ સેટ કવર (સેટ કવર માટે પ્રમાણભૂત પૂર્ણાંક રેખીય પ્રોગ્રામનો ઉકેલ) લઘુતમ-ખર્ચ અપૂર્ણાંક સેટ કવરની ગણતરી કરો (એલ. પી. છૂટછાટ માટે શ્રેષ્ઠ ઉકેલ). જવા દો. દરેક માટે દો. દરેક માટેઃ ચાલો. (તેમાં હજુ સુધી નક્કી ન થયેલા સમૂહો છે.) જો પછી સુયોજિત હોય, તો અન્યથા સુયોજિત કરો અને. (તેમાં હજુ સુધી આવરી ન લેવાયેલા ઘટકો છે.) પાછા આવો. લેમ્મા (અલ્ગોરિધમ માટે અંદાજ ગેરંટી) ઉપરનું અલ્ગોરિધમ કોઈપણ (અપૂર્ણાંક) સેટ કવરની લઘુતમ કિંમતના મોટા ભાગના સમયે ખર્ચનું સેટ કવર આપે છે. સાબિતી અલ્ગોરિધમ એ સુનિશ્ચિત કરે છે કે, ની શરતી અપેક્ષા દરેક પુનરાવર્તન પર વધતી નથી. આ શરતી અપેક્ષા શરૂઆતમાં 1 કરતા ઓછી હોવાથી (અગાઉ બતાવ્યા પ્રમાણે), અલ્ગોરિધમ એ સુનિશ્ચિત કરે છે કે શરતી અપેક્ષા 1 કરતા ઓછી રહે. નિષ્ફળતાની શરતી સંભાવના મોટાભાગે શરતી અપેક્ષા હોવાથી, આ રીતે અલ્ગોરિધમ એ સુનિશ્ચિત કરે છે કે નિષ્ફળતાની શરતી સંભાવના 1 થી ઓછી રહે. આમ, અંતે, જ્યારે બધી પસંદગીઓ નક્કી કરવામાં આવે છે, ત્યારે અલ્ગોરિધમ સફળ પરિણામ સુધી પહોંચે છે. એટલે કે, ઉપરનું અલ્ગોરિધમ કોઈપણ (અપૂર્ણાંક) સેટ કવરની લઘુતમ કિંમતના મોટા ભાગના સમયે ખર્ચનું સેટ કવર આપે છે. ટિપ્પણીઓ ઉપરના ઉદાહરણમાં, અલ્ગોરિધમને રેન્ડમ ચલની શરતી અપેક્ષા દ્વારા માર્ગદર્શન આપવામાં આવ્યું હતું. કેટલાક કિસ્સાઓમાં, ચોક્કસ શરતી અપેક્ષાને બદલે, કેટલીક શરતી અપેક્ષા પર ઉપલા બાઉન્ડ (અથવા કેટલીકવાર નીચલા બાઉન્ડ) નો ઉપયોગ કરવામાં આવે છે. આને નિરાશાવાદી અંદાજકાર કહેવામાં આવે છે. સંભવિત પદ્ધતિની અન્ય એપ્લિકેશનો સાથે સરખામણી રેન્ડમાઇઝ્ડ ગોળાકાર પગલું સંભવિત પદ્ધતિની મોટાભાગની એપ્લિકેશનોથી બે બાબતોમાં અલગ છેઃ ગોળાકાર પગલાની ગણતરીની જટિલતા મહત્વપૂર્ણ છે. તે ઉપવાસ દ્વારા અમલમાં મૂકવા યોગ્ય હોવું જોઈએ (દા. ત. બહુપદી સમય) અલ્ગોરિધમ. રેન્ડમ પ્રયોગ અંતર્ગત સંભાવના વિતરણ એ સમસ્યાના ઉદાહરણમાં છૂટછાટના ઉકેલનું કાર્ય છે. આ હકીકત અંદાજિત અલ્ગોરિધમની કામગીરીની બાંયધરી સાબિત કરવા માટે નિર્ણાયક છે---એટલે કે, કોઈપણ સમસ્યાના ઉદાહરણ માટે, અલ્ગોરિધમ એક ઉકેલ આપે છે જે તે ચોક્કસ ઉદાહરણ માટે શ્રેષ્ઠ ઉકેલનો અંદાજ આપે છે. તેની સરખામણીમાં, સંયોજનમાં સંભવિત પદ્ધતિની એપ્લિકેશનો સામાન્ય રીતે માળખાઓનું અસ્તિત્વ દર્શાવે છે જેની લાક્ષણિકતાઓ ઇનપુટના અન્ય પરિમાણો પર આધારિત હોય છે. ઉદાહરણ તરીકે, તુરાનના પ્રમેયને ધ્યાનમાં લો, જેને "સરેરાશ ડિગ્રીના શિરોબિંદુઓ સાથેનો કોઈપણ આલેખ ઓછામાં ઓછો કદનો સ્વતંત્ર સમૂહ હોવો જોઈએ" તરીકે વર્ણવી શકાય છે. (તુરાનના પ્રમેયના સંભવિત પુરાવા માટે આ જુઓ.) જ્યારે એવા આલેખ છે કે જેના માટે આ બાઉન્ડ ચુસ્ત છે, ત્યાં એવા આલેખ પણ છે કે જે તેના કરતા ઘણા મોટા સ્વતંત્ર સેટ ધરાવે છે. આમ, આલેખમાં તુરાનના પ્રમેય દ્વારા અસ્તિત્વમાં દર્શાવવામાં આવેલા સ્વતંત્ર સમૂહનું કદ, સામાન્ય રીતે, તે આલેખ માટેના મહત્તમ સ્વતંત્ર સમૂહ કરતાં ઘણું નાનું હોઈ શકે છે. રેખીય પ્રોગ્રામને હલ કર્યા વિના શરતી સંભાવનાઓની પદ્ધતિ રેન્ડમાઇઝ્ડ રાઉન્ડિંગ પણ જુઓ. સંદર્ભો. વધુ વાંચન એલ્ગોરિધમ્સ સંભવિત દલીલો