Randomized rounding
کمپیوٹر سائنس اور آپریشنز ریسرچ میں، بے ترتیب راؤنڈنگ تخمینہ الگورتھم کو ڈیزائن کرنے اور تجزیہ کرنے کے لیے ایک وسیع پیمانے پر استعمال ہونے والا نقطہ نظر ہے۔ بہت سے مشترکہ اصلاح کے مسائل کو درست طریقے سے حل کرنے کے لیے کمپیوٹیشنل طور پر ناقابل حل ہیں۔ اس طرح کے مسائل کے لیے، بے ترتیب راؤنڈنگ کو تیز (کثیر الجہتی وقت) تخمینہ الگورتھم کو ڈیزائن کرنے کے لیے استعمال کیا جا سکتا ہے-یعنی، الگورتھم جو کسی بھی ان پٹ کو دیکھتے ہوئے تقریبا بہترین حل واپس کرنے کی ضمانت دیتے ہیں۔ بے ترتیب راؤنڈنگ کا بنیادی خیال یہ ہے کہ مسئلے میں نرمی کے بہترین حل کو اصل مسئلے کے تقریبا بہترین حل میں تبدیل کیا جائے۔ نتیجے میں الگورتھم کا تجزیہ عام طور پر امکانی طریقہ استعمال کرتے ہوئے کیا جاتا ہے۔ جائزہ بنیادی نقطہ نظر کے تین مراحل ہیں: انٹیجر لینیر پروگرام (آئی ایل پی) کے طور پر حل کیے جانے والے مسئلے کی تشکیل کریں۔ آئی ایل پی کے لکیری پروگرامنگ ریلیکسشن (ایل پی) کے لیے ایک بہترین فریکشنل حل کا حساب لگائیں۔ ایل پی کے فریکشنل حل کو آئی ایل پی کے انٹیجر حل میں گول کریں۔ (اگرچہ یہ نقطہ نظر عام طور پر لکیری پروگراموں کے ساتھ لاگو ہوتا ہے، لیکن بعض اوقات دیگر قسم کی نرمی بھی استعمال کی جاتی ہے۔ مثال کے طور پر، دیکھیں گومینس اور ولیمسن کا سیمی ڈفائنٹ پروگرامنگ پر مبنی میکس کٹ تخمینہ الگورتھم۔) پہلے مرحلے میں، چیلنج ایک مناسب عدد لکیری پروگرام کا انتخاب کرنا ہے۔ لکیری پروگرامنگ سے واقفیت، خاص طور پر لکیری پروگراموں اور انٹیجر لکیری پروگراموں کا استعمال کرتے ہوئے ماڈلنگ، ضروری ہے۔ بہت سے مسائل کے لیے، ایک قدرتی عدد لکیری پروگرام ہے جو اچھی طرح سے کام کرتا ہے، جیسے کہ نیچے سیٹ کور کی مثال میں۔ (انٹیجر لکیری پروگرام میں ایک چھوٹا سا انٹیگریلیٹی گیپ ہونا چاہیے ؛ درحقیقت بے ترتیب راؤنڈنگ اکثر انٹیگریلیٹی گیپس پر حدود ثابت کرنے کے لیے استعمال ہوتی ہے۔) دوسرے مرحلے میں، زیادہ سے زیادہ فریکشنل حل کو عام طور پر کسی بھی معیاری لکیری پروگرامنگ الگورتھم کا استعمال کرتے ہوئے کثیر الجہتی وقت میں شمار کیا جا سکتا ہے۔ تیسرے مرحلے میں، فریکشنل حل کو ایک انٹیجر حل میں تبدیل کیا جانا چاہیے (اور اس طرح اصل مسئلے کا حل)۔ اسے فریکشنل حل کو گول کرنا کہا جاتا ہے۔ نتیجے میں آنے والے انٹیجر حل کی لاگت (ثابت طور پر) فریکشنل حل کی لاگت سے زیادہ نہیں ہونی چاہیے۔ یہ اس بات کو یقینی بنائے گا کہ انٹیجر حل کی لاگت زیادہ سے زیادہ انٹیجر حل کی لاگت سے زیادہ نہیں ہے۔ تیسرا مرحلہ (راؤنڈنگ) کرنے کے لیے استعمال ہونے والی اہم تکنیک بے ترتیب کاری کا استعمال کرنا ہے، اور پھر راؤنڈنگ کی وجہ سے لاگت میں اضافے کو پابند کرنے کے لیے ممکنہ دلائل کا استعمال کرنا ہے (کمبینٹوریکس سے ممکنہ طریقہ کار پر عمل کرنا)۔ اس میں، ممکنہ دلائل مطلوبہ خصوصیات کے ساتھ مجرد ڈھانچوں کے وجود کو ظاہر کرنے کے لیے استعمال کیے جاتے ہیں۔ اس تناظر میں، مندرجہ ذیل کو ظاہر کرنے کے لیے اس طرح کے دلائل کا استعمال کیا جاتا ہے: ایل پی کے کسی بھی فریکشنل حل کو دیکھتے ہوئے، مثبت امکان کے ساتھ بے ترتیب گول کرنے کا عمل ایک انٹیجر حل پیدا کرتا ہے جو کچھ مطلوبہ معیار کے مطابق ہوتا ہے۔ آخر میں، تیسرے مرحلے کو کمپیوٹیشنل طور پر موثر بنانے کے لیے، یا تو یہ ظاہر ہوتا ہے کہ یہ زیادہ امکان کے ساتھ لگ بھگ ہے (تاکہ مرحلہ بے ترتیب رہ سکے) یا عام طور پر مشروط امکانات کے طریقہ کار کا استعمال کرتے ہوئے راؤنڈنگ مرحلے کو بے ترتیب کر دیتا ہے۔ مؤخر الذکر طریقہ بے ترتیب راؤنڈنگ کے عمل کو ایک موثر تعیناتی عمل میں تبدیل کرتا ہے جس کے اچھے نتائج تک پہنچنے کی ضمانت ہوتی ہے۔ مثال: سیٹ کور کا مسئلہ مندرجہ ذیل مثال سے پتہ چلتا ہے کہ سیٹ کور کے مسئلے کے لیے ایک تخمینہ الگورتھم ڈیزائن کرنے کے لیے بے ترتیب راؤنڈنگ کو کس طرح استعمال کیا جا سکتا ہے۔ کائنات پر سیٹ کور کی کسی بھی مثال کو ٹھیک کریں۔ فریکشنل حل کا حساب لگانا مرحلہ 1 کے لیے، آئی پی کو اس مثال کے لیے سیٹ کور کے لیے معیاری انٹیجر لکیری پروگرام ہونے دیں۔ مرحلہ 2 کے لیے، ایل پی کو آئی پی کی لکیری پروگرامنگ نرمی ہونے دیں، اور کسی بھی معیاری لکیری پروگرامنگ الگورتھم کا استعمال کرتے ہوئے ایل پی کے لیے ایک بہترین حل کا حساب لگائیں۔ اس میں ان پٹ سائز میں کثیر الجہتی وقت لگتا ہے۔ ایل پی کے قابل عمل حل وہ ویکٹر ہیں جو ہر سیٹ کو غیر منفی وزن تفویض کرتے ہیں، جیسے کہ، ہر عنصر کے لیے، احاطہ کرتا ہے-- سیٹ پر تفویض کردہ کل وزن کم از کم 1 ہے، یعنی، زیادہ سے زیادہ حل ایک قابل عمل حل ہے جس کی قیمت کم سے کم ہے۔ نوٹ کریں کہ کوئی بھی سیٹ کور ایک قابل عمل حل فراہم کرتا ہے (جہاں کے لیے، بصورت دیگر)۔ اس کی لاگت قیمت کے برابر ہے، یعنی، دوسرے لفظوں میں، لکیری پروگرام ایل پی دیئے گئے سیٹ کور کے مسئلے میں نرمی ہے۔ چونکہ ایل پی کے قابل عمل حل میں کم سے کم لاگت ہوتی ہے، اس لیے لاگت زیادہ سے زیادہ سیٹ کور کی لاگت پر کم ہوتی ہے۔ بے ترتیب راؤنڈنگ مرحلہ مرحلہ 3 میں، ہمیں کم از کم لاگت والے فریکشنل سیٹ کور کو ایک قابل عمل انٹیجر حل (ایک حقیقی سیٹ کور کے مطابق) میں تبدیل کرنا چاہیے۔ راؤنڈنگ مرحلے سے ایسا پیدا ہونا چاہیے کہ، مثبت امکان کے ساتھ، لاگت کی لاگت کے ایک چھوٹے سے عنصر کے اندر لاگت ہو۔ پھر (چونکہ لاگت زیادہ سے زیادہ سیٹ کور کی لاگت پر کم پابند ہے)، لاگت زیادہ سے زیادہ لاگت کے ایک چھوٹے سے عنصر کے اندر ہوگی۔ ابتدائی نقطہ کے طور پر، سب سے زیادہ قدرتی راؤنڈنگ اسکیم پر غور کریں: باری باری ہر سیٹ کے لیے، امکان کے ساتھ لیں، بصورت دیگر لیں۔ اس راؤنڈنگ اسکیم کے ساتھ، منتخب کردہ سیٹوں کی متوقع لاگت زیادہ سے زیادہ، فریکشنل کور کی لاگت ہے۔ یہ اچھی بات ہے۔ بدقسمتی سے کوریج اچھی نہیں ہے۔ جب متغیرات چھوٹے ہوتے ہیں، تو اس بات کا امکان ہے کہ کسی عنصر کا احاطہ نہیں کیا گیا ہے، تو توقع میں عناصر کا صرف ایک مستقل حصہ احاطہ کیا جائے گا۔ اعلی امکان کے ساتھ ہر عنصر کا احاطہ کرنے کے لیے، معیاری راؤنڈنگ اسکیم پہلے ایک مناسب عنصر کے ذریعے راؤنڈنگ کے امکانات کو بڑھاتی ہے۔ یہاں معیاری راؤنڈنگ اسکیم ہے: ایک پیرامیٹر طے کریں۔ باری باری ہر سیٹ کے لیے، امکان کے ساتھ لیں، بصورت دیگر لیں۔ امکانات کو بڑھانا متوقع لاگت میں اضافہ کرتا ہے، لیکن تمام عناصر کی کوریج کو ممکنہ بناتا ہے۔ خیال یہ ہے کہ جتنا ممکن ہو اتنا چھوٹا انتخاب کیا جائے تاکہ تمام عناصر ثابت طور پر غیر صفر امکان سے ڈھکے ہوں۔ یہاں ایک تفصیلی تجزیہ ہے۔ لیما (راؤنڈنگ اسکیم کے لیے تخمینہ گارنٹی) ٹھیک کریں۔ مثبت امکان کے ساتھ، راؤنڈنگ اسکیم زیادہ سے زیادہ لاگت کا ایک سیٹ کور واپس کرتی ہے (اور اس طرح لاگت کے اوقات زیادہ سے زیادہ سیٹ کور کی لاگت)۔ (نوٹ: احتیاط کے ساتھ اسے کم کیا جا سکتا ہے۔) ثبوت بے ترتیب راؤنڈنگ اسکیم کی پیداوار میں مطلوبہ خصوصیات ہوتی ہیں جب تک کہ مندرجہ ذیل "خراب" واقعات میں سے کوئی بھی نہ ہو: حد سے تجاوز کی لاگت، یا کسی عنصر کے لیے، احاطہ کرنے میں ناکام رہتی ہے۔ ہر ایک کی توقع زیادہ سے زیادہ ہوتی ہے۔ توقع کی لکیری سے، توقع زیادہ سے زیادہ ہوتی ہے۔ اس طرح، مارکوف کی عدم مساوات کے مطابق، اوپر دیے گئے پہلے برے واقعے کا امکان زیادہ سے زیادہ ہے۔ بقیہ خراب واقعات کے لیے (ہر عنصر کے لیے ایک)، نوٹ کریں کہ، چونکہ کسی بھی عنصر کے لیے، وہ امکان جس کا احاطہ نہیں کیا گیا ہے (یہ عدم مساوات کا استعمال کرتا ہے، جو اس کے لیے سخت ہے۔) اس طرح، ہر عنصر کے لیے، عنصر کا احاطہ نہ ہونے کا امکان اس سے کم ہے۔ یونین باؤنڈ کی طرف سے، امکان ہے کہ ایک برا واقعہ واقع ہوتا ہے اس سے کم ہے۔ اس طرح، مثبت امکان کے ساتھ کوئی برے واقعات نہیں ہوتے ہیں اور یہ زیادہ سے زیادہ لاگت کا ایک سیٹ کور ہے۔ مشروط امکانات کے طریقہ کار کا استعمال کرتے ہوئے کیو ای ڈی ڈیرینڈومائزیشن مندرجہ بالا لیما لاگت کے ایک سیٹ کور کے وجود کو ظاہر کرتا ہے)۔ اس تناظر میں ہمارا مقصد ایک موثر تخمینہ الگورتھم ہے، نہ کہ صرف وجود کا ثبوت، لہذا ہم مکمل نہیں ہوئے ہیں۔ ایک طریقہ یہ ہوگا کہ تھوڑا سا اضافہ کیا جائے، پھر دکھایا جائے کہ کامیابی کا امکان کم از کم 1/4 ہے۔ اس ترمیم کے ساتھ، بے ترتیب راؤنڈنگ مرحلے کو چند بار دہرانا اعلی امکان کے ساتھ کامیاب نتیجہ کو یقینی بنانے کے لیے کافی ہے۔ یہ نقطہ نظر تخمینہ تناسب کو کمزور کر دیتا ہے۔ اس کے بعد ہم ایک مختلف نقطہ نظر کی وضاحت کرتے ہیں جو ایک تعیناتی الگورتھم فراہم کرتا ہے جو اوپر موجود وجود کے ثبوت کے تخمینہ تناسب سے ملنے کی ضمانت دیتا ہے۔ اس نقطہ نظر کو مشروط امکانات کا طریقہ کہا جاتا ہے۔ تعیناتی الگورتھم بے ترتیب راؤنڈنگ اسکیم کی تقلید کرتا ہے: یہ ہر سیٹ پر باری باری غور کرتا ہے، اور انتخاب کرتا ہے۔ لیکن ہر انتخاب کو تصادفی طور پر اس کی بنیاد پر کرنے کے بجائے، یہ فیصلہ کن طور پر انتخاب کرتا ہے، تاکہ ناکامی کے مشروط امکان کو، اب تک کے انتخاب کو دیکھتے ہوئے، 1 سے نیچے رکھا جا سکے۔ ناکامی کے مشروط امکان کو محدود کرنا ہم ہر متغیر کو باری باری ترتیب دینے کے قابل ہونا چاہتے ہیں تاکہ ناکامی کے مشروط امکان کو 1 سے نیچے رکھا جا سکے۔ ایسا کرنے کے لیے، ہمیں ناکامی کے مشروط امکان پر ایک اچھی پابندی کی ضرورت ہے۔ باؤنڈ اصل وجود کے ثبوت کو بہتر بنا کر آئے گا۔ یہ ثبوت بے ترتیب متغیر کی توقع سے ناکامی کے امکان کو مضمر طور پر پابند کرتا ہے، جہاں عناصر کا مجموعہ آخر میں بے نقاب رہ جاتا ہے۔ بے ترتیب متغیر تھوڑا سا پراسرار لگ سکتا ہے، لیکن یہ ممکنہ ثبوت کو منظم طریقے سے ظاہر کرتا ہے۔ پہلی اصطلاح مارکوف کی عدم مساوات کو پہلے خراب واقعے کے امکان کو پابند کرنے کے لیے لاگو کرنے سے آتی ہے (لاگت بہت زیادہ ہے)۔ اگر قیمت بہت زیادہ ہے تو یہ کم از کم 1 کا حصہ ڈالتا ہے۔ دوسری اصطلاح دوسری قسم کے برے واقعات (بے نقاب عناصر) کی تعداد شمار کرتی ہے۔ اگر کسی عنصر کو بے نقاب چھوڑ دیتا ہے تو یہ کم از کم 1 کا حصہ ڈالتا ہے۔ اس طرح، کسی بھی نتیجے میں جہاں 1 سے کم ہو، تمام عناصر کا احاطہ کرنا چاہیے اور لیما سے مطلوبہ حد کو پورا کرنے والی لاگت ہونی چاہیے۔ مختصرا، اگر راؤنڈنگ مرحلہ ناکام ہوجاتا ہے، تو۔ اس کا مطلب ہے (مارکوف کی عدم مساوات سے) جو ناکامی کے امکان پر ایک اوپری حد ہے۔ نوٹ کریں کہ اوپر دی گئی دلیل لیما کے ثبوت میں پہلے سے ہی مضمر ہے، جو حساب سے بھی ظاہر ہوتی ہے۔ مشروط امکانات کے طریقہ کار کو لاگو کرنے کے لیے، ہمیں راؤنڈنگ مرحلہ آگے بڑھتے ہی ناکامی کے مشروط امکان کو پابند کرنے کے لیے دلیل کو بڑھانے کی ضرورت ہے۔ عام طور پر، یہ ایک منظم طریقے سے کیا جا سکتا ہے، حالانکہ یہ تکنیکی طور پر تکلیف دہ ہو سکتا ہے۔ تو، ناکامی کے مشروط امکان کے بارے میں کیا جیسا کہ راؤنڈنگ مرحلہ سیٹوں کے ذریعے دہرایا جاتا ہے؟ چونکہ کسی بھی نتیجے میں جہاں راؤنڈنگ مرحلہ ناکام ہوجاتا ہے، مارکوف کی عدم مساوات کی وجہ سے، ناکامی کا مشروط امکان زیادہ سے زیادہ کی مشروط توقع ہوتی ہے۔ اگلا ہم کی مشروط توقع کا حساب لگاتے ہیں، بالکل اسی طرح جیسے ہم نے اصل ثبوت میں کی غیر مشروط توقع کا حساب لگایا تھا۔ کچھ تکرار کے اختتام پر گول کرنے کے عمل کی حالت پر غور کریں۔ آئیے اب تک زیر غور سیٹوں کی نشاندہی کریں (پہلے سیٹوں میں)۔ آئیے (جزوی طور پر تفویض کردہ) ویکٹر کی نشاندہی کریں (لہذا صرف اس صورت میں طے کیا جاتا ہے اگر)۔ ہر سیٹ کے لیے، اس امکان کو ظاہر کریں جس کے ساتھ 1 مقرر کیا جائے گا۔ ان عناصر کو شامل کریں جو ابھی تک ڈھکے ہوئے نہیں ہیں۔ پھر کی مشروط توقع، اب تک کیے گئے انتخاب کو دیکھتے ہوئے، یعنی دی گئی، نوٹ ہے جس کا تعین تکرار کے بعد ہی ہوتا ہے۔ ناکامی کے مشروط امکان کو 1 سے نیچے رکھنا ناکامی کے مشروط امکان کو 1 سے نیچے رکھنے کے لیے، 1 سے نیچے کی مشروط توقع کو برقرار رکھنا کافی ہے۔ ایسا کرنے کے لیے، یہ بڑھنے کی مشروط توقع کو برقرار رکھنے کے لیے کافی ہے۔ الگورتھم یہی کرے گا۔ یہ ہر تکرار میں اس بات کو یقینی بنانے کے لیے سیٹ کیا جائے گا کہ (کہاں)۔ تیسری تکرار میں، الگورتھم اس بات کو یقینی بنانے کے لیے کیسے سیٹ کر سکتا ہے؟ یہ پتہ چلتا ہے کہ یہ آسانی سے سیٹ کیا جا سکتا ہے تاکہ کے نتیجے میں قیمت کو کم سے کم کیا جا سکے۔ یہ دیکھنے کے لیے کہ کیوں، اس وقت پر توجہ مرکوز کریں جب تکرار شروع ہوتی ہے۔ اس وقت، طے کیا جاتا ہے، لیکن ابھی تک طے نہیں کیا گیا ہے---یہ دو ممکنہ اقدار لے سکتا ہے اس پر منحصر ہے کہ تکرار میں کیسے سیٹ کیا جاتا ہے۔ آئیے کی قدر کو ظاہر کرتے ہیں۔ چلو اور، کی دو ممکنہ اقدار کی نشاندہی کرتے ہیں، اس پر منحصر ہے کہ بالترتیب 0، یا 1 پر سیٹ کیا گیا ہے۔ مشروط توقع کی تعریف کے مطابق، چونکہ دو مقداروں کی اوسط اوسط ہمیشہ کم از کم ان دو مقداروں میں سے کم از کم ہوتی ہے، اس کے بعد یہ ہوتا ہے کہ اس طرح، ترتیب اس بات کی ضمانت دے گی کہ اس کے نتیجے میں ہونے والی قیمت کو کم سے کم کیا جائے۔ الگورتھم یہی کرے گا۔ تفصیل سے، اس کا کیا مطلب ہے؟ فنکشن کے طور پر سمجھا جاتا ہے (دیگر تمام مقداروں کے ساتھ طے شدہ) ایک لکیری فنکشن ہے، اور اس فنکشن میں کا گتانک ہے۔ اس طرح، الگورتھم کو 0 پر سیٹ کرنا چاہیے اگر یہ اظہار مثبت ہے، اور بصورت دیگر 1۔ یہ مندرجہ ذیل الگورتھم دیتا ہے۔ سیٹ کور ان پٹ کے لیے بے ترتیب گول الگورتھم: سیٹ سسٹم، کائنات، لاگت ویکٹر آؤٹ پٹ: سیٹ کور (سیٹ کور کے لیے معیاری انٹیجر لکیری پروگرام کا حل) ایک کم لاگت والے فریکشنل سیٹ کور کا حساب لگائیں (ایل پی نرمی کا ایک بہترین حل)۔ جانے دیں۔ ہر ایک کے لیے چھوڑ دیں۔ ہر ایک کے لیے: کرنے دیں۔ (ابھی تک طے شدہ سیٹ پر مشتمل نہیں ہے۔) اگر پھر سیٹ کریں، ورنہ سیٹ کریں اور۔ (ان عناصر پر مشتمل ہے جو ابھی تک ڈھکے نہیں ہیں۔) واپسی۔ لیما (الگورتھم کے لیے تخمینہ کی ضمانت) مندرجہ بالا الگورتھم کسی بھی (فریکشنل) سیٹ کور کی کم از کم لاگت کے زیادہ تر اوقات میں لاگت کا ایک سیٹ کور واپس کرتا ہے۔ ثبوت الگورتھم اس بات کو یقینی بناتا ہے کہ،، کی مشروط توقع ہر تکرار پر نہیں بڑھتی ہے۔ چونکہ یہ مشروط توقع ابتدائی طور پر 1 سے کم ہے (جیسا کہ پہلے دکھایا گیا ہے)، الگورتھم اس بات کو یقینی بناتا ہے کہ مشروط توقع 1 سے نیچے رہے۔ چونکہ ناکامی کا مشروط امکان زیادہ سے زیادہ کی مشروط توقع ہے، اس طرح الگورتھم اس بات کو یقینی بناتا ہے کہ ناکامی کا مشروط امکان 1 سے نیچے رہے۔ اس طرح، آخر میں، جب تمام انتخاب کا تعین کیا جاتا ہے، الگورتھم ایک کامیاب نتیجہ تک پہنچ جاتا ہے۔ یعنی، اوپر کا الگورتھم زیادہ تر اوقات میں کسی بھی (فریکشنل) سیٹ کور کی کم از کم لاگت پر لاگت کا ایک سیٹ کور واپس کرتا ہے۔ تبصرے مندرجہ بالا مثال میں، الگورتھم کو بے ترتیب متغیر کی مشروط توقع سے رہنمائی حاصل تھی۔ کچھ معاملات میں، عین مطابق مشروط توقع کے بجائے، کچھ مشروط توقع پر ایک اوپری حد (یا بعض اوقات نچلی حد) استعمال کی جاتی ہے۔ اسے مایوس کن تخمینہ کار کہا جاتا ہے۔ ممکنہ طریقہ کار کی دیگر ایپلی کیشنز سے موازنہ بے ترتیب راؤنڈنگ مرحلہ ممکنہ طریقہ کار کی زیادہ تر ایپلی کیشنز سے دو لحاظ سے مختلف ہے: راؤنڈنگ مرحلے کی کمپیوٹیشنل پیچیدگی اہم ہے۔ اسے روزہ کے ذریعے قابل عمل ہونا چاہیے (مثال کے طور پر۔ کثیر الجہتی وقت) الگورتھم۔ بے ترتیب تجربے کی بنیاد پر امکان کی تقسیم مسئلہ کی مثال میں نرمی کے حل کا ایک کام ہے۔ یہ حقیقت تخمینہ الگورتھم کی کارکردگی کی ضمانت کو ثابت کرنے کے لیے اہم ہے---یعنی، کہ کسی بھی مسئلے کی مثال کے لیے، الگورتھم ایک ایسا حل واپس کرتا ہے جو اس مخصوص مثال کے لیے زیادہ سے زیادہ حل کا تخمینہ لگاتا ہے۔ اس کے مقابلے میں، امتزاج میں ممکنہ طریقہ کار کی ایپلی کیشنز عام طور پر ان ڈھانچوں کے وجود کو ظاہر کرتی ہیں جن کی خصوصیات ان پٹ کے دیگر پیرامیٹرز پر منحصر ہوتی ہیں۔ مثال کے طور پر، توران کے نظریہ پر غور کریں، جسے اس طرح بیان کیا جا سکتا ہے کہ "اوسط ڈگری کے عمودی حصوں والے کسی بھی گراف میں کم از کم سائز کا ایک آزاد مجموعہ ہونا چاہیے۔ (ٹورن کے نظریہ کے ممکنہ ثبوت کے لیے یہ دیکھیں۔) اگرچہ ایسے گراف ہیں جن کے لیے یہ باؤنڈ تنگ ہے، لیکن ایسے گراف بھی ہیں جن کے آزاد سیٹ اس سے بہت بڑے ہیں۔ اس طرح، گراف میں توران کے نظریہ کے ذریعہ ظاہر کردہ آزاد سیٹ کا سائز، عام طور پر، اس گراف کے زیادہ سے زیادہ آزاد سیٹ سے بہت چھوٹا ہو سکتا ہے۔ لکیری پروگرام کو حل کیے بغیر مشروط امکانات کے بے ترتیب گول کرنے کا طریقہ بھی دیکھیں۔ حوالہ جات۔ مزید پڑھنا الگورتھم ممکنہ دلائل