Balanced number partitioning
بیلنسڈ نمبر پارٹیشننگ ملٹی وے نمبر پارٹیشننگ کی ایک قسم ہے جس میں ہر سیٹ کے لیے مختص آئٹمز کی تعداد پر رکاوٹیں ہوتی ہیں۔ دشواری کا ان پٹ مختلف سائز کی n آئٹمز کا ایک سیٹ ہے، اور دو انٹیجرز m، k۔ آؤٹ پٹ آئٹمز کو m سبسیٹس میں تقسیم کرنا ہے، جیسے کہ ہر سبسیٹ میں آئٹمز کی تعداد زیادہ سے زیادہ k ہو۔ اس کے تابع، یہ ضروری ہے کہ m سبسیٹس میں سائز کے مجموعے ہر ممکن حد تک ملتے جلتے ہوں۔ ایک مثال ایپلی کیشن یکساں مشینوں کا شیڈولنگ ہے جہاں ہر مشین میں ایک جاب کیو ہوتا ہے جو زیادہ سے زیادہ k جابز کو برقرار رکھ سکتا ہے۔ اس مسئلے کا اطلاق وی ایل ایس آئی چپس کی تیاری اور لچکدار مینوفیکچرنگ سسٹم میں مشینوں کو ٹولز تفویض کرنے میں بھی ہوتا ہے۔ زیادہ سے زیادہ کام کے شیڈولنگ کے مسائل کے لیے معیاری تھری فیلڈ نوٹیشن میں، سب سے بڑی رقم کو کم کرنے کے مسئلے کو بعض اوقات "P | #≤ k | Cmax" سے ظاہر کیا جاتا ہے۔ درمیانی فیلڈ "#≤ k" اس بات کی نشاندہی کرتا ہے کہ ہر مشین میں جابز کی تعداد زیادہ سے زیادہ k ہونی چاہیے۔ یہ غیر محدود ورژن کے برعکس ہے، جسے "" سے ظاہر کیا جاتا ہے۔ دو طرفہ متوازن تقسیم ایک عام خاص معاملہ جسے دو طرفہ متوازن تقسیم کہا جاتا ہے وہ ہے جب دو ذیلی سیٹ (m = 2) ہونے چاہئیں۔ دونوں ذیلی سیٹوں میں فرش (n/2) اور چھت (n/2) اشیاء ہونی چاہئیں۔ یہ تقسیم کے مسئلے کا ایک متغیر ہے۔ یہ فیصلہ کرنا این پی مشکل ہے کہ آیا کوئی ایسی تقسیم موجود ہے جس میں دونوں ذیلی سیٹوں میں رقم برابر ہو۔ مسئلہ [ایس پی 12] دیکھیں۔ بہت سے الگورتھم ہیں جن کا مقصد ایک متوازن پارٹیشن تلاش کرنا ہے جس میں رقم ہر ممکن حد تک برابر ہو۔ کوفمین، فریڈرکسن اور لیوکر ایل پی ٹی الگورتھم (جسے آر ایل پی ٹی کہا جاتا ہے) کا ایک محدود ورژن پیش کرتے ہیں، جس میں ان پٹ جوڑوں میں تفویض کیے جاتے ہیں۔ جب ان پٹ یکساں طور پر تقسیم شدہ بے ترتیب متغیر ہوتے ہیں، تو آر ایل پی ٹی کا متوقع سب سے بڑا مجموعہ بالکل ہوتا ہے۔ متوقع کام کا فرق (سب سے بڑی اور سب سے چھوٹی رقم کے درمیان فرق) ہے۔ لیوکر ایل ڈی ایم الگورتھم کی ایک قسم پیش کرتا ہے (جسے جوڑی کے لحاظ سے تفریق کا طریقہ (پی ڈی ایم) کہا جاتا ہے)۔ اس کے متوقع کام کا فرق ہے۔ سائی ایک الگورتھم پیش کرتی ہے جسے محدود سب سے بڑا فرق (آر ایل ڈی) کہا جاتا ہے۔ اس کے کام کا فرق تقریبا یقینی ہے۔ یاکر m = 2 کے لیے ایل ڈی ایم الگورتھم کا ایک متوازن ورژن پیش کرتا ہے، جسے بی ایل ڈی ایم کہا جاتا ہے۔ اس کے متوقع کام کا فرق ہے۔ مرٹنز متوازن دو طرفہ تقسیم کے لیے کسی بھی وقت ایک مکمل الگورتھم پیش کرتا ہے۔ یہ بی ایل ڈی ایم الگورتھم کو مکمل-کرمارکر-کارپ الگورتھم کے ساتھ جوڑتا ہے۔ متوازن ٹرپلٹ پارٹیشننگ ایک اور خاص معاملہ جسے 3-پارٹیشننگ کہا جاتا ہے وہ ہے جب ہر ذیلی سیٹ میں آئٹمز کی تعداد زیادہ سے زیادہ 3 (k = 3) ہونی چاہیے۔ یہ فیصلہ کرنا کہ آیا مساوی رقم کے ساتھ ایسی پارٹیشن موجود ہے، بالکل 3-پارٹیشن کا مسئلہ ہے، جسے مضبوطی سے این پی-ہارڈ کہا جاتا ہے۔ تخمینہ الگورتھم موجود ہیں جن کا مقصد ایک ایسی پارٹیشن تلاش کرنا ہے جس میں رقم ہر ممکن حد تک برابر ہو۔ کیلر اور ووینجر ایل پی ٹی الگورتھم کو ٹرپلٹ پارٹیشننگ کے مطابق ڈھالتے ہیں (جہاں زیادہ سے زیادہ 3 * میٹر آئٹمز ہوتے ہیں، اور ہر سب سیٹ میں زیادہ سے زیادہ 3 آئٹمز ہونے چاہئیں)۔ ان کے الگورتھم کو ترمیم شدہ-ایل پی ٹی یا ایم ایل پی ٹی کہا جاتا ہے۔ یہ بڑی سے چھوٹی اشیاء کا آرڈر دیتا ہے، اور ہر چیز کو ان ڈبوں میں سب سے چھوٹی رقم کے ساتھ ڈبے میں ڈالتا ہے جن میں 3 سے کم اشیاء ہوتی ہیں۔ وہ ظاہر کرتے ہیں کہ ایم ایل پی ٹی الگورتھم زیادہ تر کم از کم سب سے بڑی رقم حاصل کرتا ہے، جو کہ وہی تخمینہ تناسب ہے جو ایل پی ٹی غیر محدود مسئلے کے لیے حاصل کرتا ہے۔ ایم ایل پی ٹی کے لیے باؤنڈ سخت ہے۔ چن، ہی اور لن دکھاتے ہیں کہ، اسی مسئلے کے لیے، ایم ایل پی ٹی کم از کم سب سے چھوٹی رقم حاصل کرتا ہے، جو دوبارہ وہی تناسب ہے جو ایل پی ٹی غیر محدود مسئلے کے لیے حاصل کرتا ہے۔ کیلر اور کوٹوف ایک مختلف الگورتھم پیش کرتے ہیں (بالکل 3 * میٹر آئٹمز کے معاملے کے لیے)، جو زیادہ سے زیادہ کم از کم سب سے بڑی رقم حاصل کرتا ہے۔ ایک زیادہ عام کیس، جسے k-پارٹیشننگ کہا جاتا ہے، وہ ہوتا ہے جب ہر ذیلی سیٹ میں آئٹمز کی تعداد زیادہ سے زیادہ k ہونی چاہیے، جہاں k کوئی مثبت عدد ہو سکتا ہے۔ بابل، کیلر اور کوٹوف ایک قسم کا مطالعہ کرتے ہیں جس میں k × m آئٹمز ہوتے ہیں (کچھ عدد k کے لیے)، اور m سیٹ میں سے ہر ایک میں بالکل k آئٹمز ہونے چاہئیں۔ وہ کم از کم سب سے بڑی رقم کا تخمینہ لگانے کے لیے کئی ہیورسٹک الگورتھم پیش کرتے ہیں: فولڈنگ الگورتھم: m = 2 کے لیے بہترین، اور عام طور پر اس کا تخمینہ تناسب سخت ہوتا ہے۔ ایکسچینج الگورتھم: سخت تخمینہ تناسب۔ یہ معلوم نہیں ہے کہ یہ کثیر الجہتی وقت میں چلتا ہے یا نہیں۔ ابتدائی دوہری الگورتھم (ایل پی ٹی اور ملٹی فٹ کا مجموعہ): زیادہ سے زیادہ تخمینہ تناسب۔ یہ k = 4 کے لیے تنگ ہوتا ہے جب m کافی بڑا ہوتا ہے ؛ عین مطابق نچلی حد ہے)۔ یہ بھی قیاس ہے کہ ترمیم شدہ-ایل پی ٹی کا تخمینہ تناسب ہے۔ فی الحال، یہ قیاس صرف k = 3 کے لیے درست معلوم ہوتا ہے۔ k> 3 کے لیے، یہ معلوم ہے کہ اس کا تخمینہ تناسب زیادہ سے زیادہ 2 ہے۔ مشیلز، کورسٹ، آرٹس، وین لیوین اور سپیکسما ایک ایسی قسم کا مطالعہ کرتے ہیں جس میں ہر ایم سیٹ میں چھت (این/ایم) یا فرش (این/ایم) آئٹمز (لہذا کے = چھت (این/ایم)) ہونا ضروری ہے۔ وہ متوازن-ایل ڈی ایم (بی ایل ڈی ایم) کو ایم = 2 سے عام ایم تک پھیلاتے ہیں۔ عمومی الگورتھم وقت کے ساتھ چلتا ہے۔ وہ ثابت کرتے ہیں کہ کم از کم سب سے بڑی رقم کے لیے اس کا تخمینہ تناسب k = 3 کے لیے بالکل 4/3، k = 4 کے لیے 19/12، k = 5 کے لیے 103/60، k = 6 کے لیے 643/360، اور k = 7 کے لیے 4603/2520 ہے۔ تناسب ایک مخلوط عدد لکیری پروگرام کو حل کرکے پایا گیا۔ عام طور پر (کسی بھی k کے لیے)، تخمینہ تناسب کم از کم اور زیادہ سے زیادہ ہوتا ہے۔ 3,4,5، 6,7 کے عین مطابق MILP نتائج نچلی حد سے مطابقت رکھتے ہیں۔ کے> 7 کے لیے، کوئی درست نتائج معلوم نہیں ہیں، لیکن نچلے اور اوپری باؤنڈ کے درمیان فرق 0.3 ٪ سے کم ہے۔ جب پیرامیٹر ذیلی سیٹوں (m) کی تعداد ہے، تو تخمینہ تناسب بالکل ہے۔ ژانگ، موراتیڈس اور پینگ ظاہر کرتے ہیں کہ بی ایل ڈی ایم اعلی کام کے فرق (سب سے زیادہ اور سب سے کم رقم کے درمیان فرق) کے ساتھ پارٹیشن دے سکتا ہے، دونوں جب ان پٹ یکساں طور پر تقسیم کیے جاتے ہیں، اور جب ان کی تقسیم منحرف ہوتی ہے۔ وہ دو متبادل تحقیقات کی تجویز کرتے ہیں: ایل آر ایم کام کے فرق کو 1/3 تک کم کر دیتا ہے جب تقسیم یکساں ہوتی ہے تو بی ایل ڈی ایم کے کام کے فرق کو ؛ جب تقسیم منحرف ہوتی ہے تو میلڈ کام کے فرق کو کم کر دیتا ہے۔ ایک ہائبرڈ الگورتھم بی ایل ڈی ایم، ایل آر ایم اور میلڈ کو یکجا کرتا ہے اور مختلف ڈیٹا کی تقسیم کے لیے متحرک طور پر ڈھال لیتا ہے۔ جب k طے کیا جاتا ہے، تو متوازن تقسیم کے لیے ہوک بوم اور شمائے کا پی ٹی اے ایس استعمال کیا جا سکتا ہے۔ جب k ان پٹ کا حصہ ہے، تو فی الحال کوئی پی ٹی اے ایس معلوم نہیں ہے۔ ڈیل امیکو اور مارٹیلو سب سے بڑی رقم کو کم کرنے کے مسئلے کا مطالعہ کرتے ہیں جب تمام سیٹوں میں آئٹمز کی تعداد زیادہ سے زیادہ k ہوتی ہے۔ وہ ظاہر کرتے ہیں کہ اس قسم کے لکیری پروگرام میں نرمی کی اتنی ہی بہترین قیمت ہوتی ہے جتنی کہ غیر محدود قسم کے ایل پی میں نرمی۔ اظہار، جہاں xi بڑے سے چھوٹے تک آرڈر کردہ ان پٹ ہیں، زیادہ سے زیادہ سب سے بڑی رقم کے لیے نچلی حد ہے، اور اس کا بدترین صورت کا تناسب دونوں اقسام میں 1/2 ہے۔ بہتر اظہار میں غیر محدود قسم میں بدترین صورت کا تناسب 2/3 اور محدود قسم میں 1/2 ہوتا ہے۔ ترمیم شدہ فہرست شیڈولنگ کا تخمینہ تناسب غیر محدود قسم کے لیے 1/2 ہے، لیکن یہ محدود قسم کے لیے 0 ہے (یہ من مانی طور پر خراب ہو سکتا ہے)۔ ترمیم شدہ ایل پی ٹی الگورتھم کا تخمینہ تناسب زیادہ سے زیادہ 2 ہے۔ وہ یہ بھی ظاہر کرتے ہیں کہ کی نچلی حد کا بدترین کارکردگی کا تناسب 3/4 ہے، اور یہ کہ ان کے پی ڈی الگورتھم کا کارکردگی کا تناسب 4/3 ہے (جب m کافی زیادہ ہے)۔ وہ، تان، جھو اور یاؤ سب سے چھوٹی رقم کو زیادہ سے زیادہ کرنے کے مسئلے پر غور کرتے ہیں۔ وہ ظاہر کرتے ہیں کہ فولڈنگ الگورتھم کا تخمینہ تناسب سخت ہے۔ وہ کم از کم بدترین صورت کے تناسب کے ساتھ ایک نیا الگورتھم، ہارمونک 1 پیش کرتے ہیں۔ یہ دونوں الگورتھم آرڈینل ہیں-وہ آئٹمز کو ان کی صحیح اقدار کے بجائے صرف ان کے درمیان ترتیب کی بنیاد پر تقسیم کرتے ہیں۔ وہ ثابت کرتے ہیں کہ کسی بھی آرڈینل الگورتھم میں سب سے چھوٹی رقم کو زیادہ سے زیادہ کرنے کے لیے زیادہ سے زیادہ تناسب ہوتا ہے۔ یہ اس بات کی نشاندہی کرتا ہے کہ ہارمونک 1 غیر علامتی طور پر بہترین ہے۔ کسی بھی فکسڈ k کے لیے، کسی بھی آرڈینل الگورتھم کا تناسب مساوات کا سب سے چھوٹا جڑ ہوتا ہے۔ جب k کا رجحان انفینیٹی کی طرف ہوتا ہے، تو یہ اوپری باؤنڈ 0 تک پہنچ جاتا ہے۔ متوازن اور غیر محدود مسائل کے درمیان تعلقات متوازن تقسیم کے مسئلے اور معیاری (غیر محدود) تقسیم کے مسئلے کے تخمینوں کے درمیان کچھ عمومی تعلقات ہیں۔ بابل، کیلر اور کوٹوف ثابت کرتے ہیں کہ غیر محدود زیادہ سے زیادہ اور محدود زیادہ سے زیادہ کے درمیان تناسب زیادہ سے زیادہ ہے، اور یہ تنگ ہے۔ کیلر اور کوٹوف ثابت کرتے ہیں کہ صلاحیت k اور تخمینہ تناسب r (کم از کم سب سے بڑی رقم کے لیے) کے ساتھ متوازن تقسیم کے لیے ہر تحقیق کو تخمینہ تناسب کے ساتھ غیر محدود تقسیم کے لیے تحقیق حاصل کرنے کے لیے استعمال کیا جا سکتا ہے۔ خاص طور پر، ٹرپلٹ پارٹیشننگ (k = 3) کے لیے ان کے-ضمیمہ الگورتھم کو تخمینہ تناسب کے ساتھ غیر محدود پارٹیشننگ کے لیے ایک تحقیق حاصل کرنے کے لیے استعمال کیا جا سکتا ہے۔ کارڈینیلیٹی کی مختلف رکاوٹیں کارڈینیلیٹی کی رکاوٹوں کو ہر ذیلی سیٹ پر مختلف رکاوٹ کی اجازت دے کر عام کیا جا سکتا ہے۔ اس قسم کو "کھلے مسائل" کے حصے میں متعارف کرایا گیا ہے، جو کی-پارٹیشننگ مسئلہ کہتے ہیں۔ وہ، تان، جھو اور یاؤ مختلف کارڈینیلیٹی رکاوٹوں کے ساتھ سب سے چھوٹی رقم کو زیادہ سے زیادہ کرنے کے لیے ہارمونک 2 نامی ایک الگورتھم پیش کرتے ہیں۔ وہ ثابت کرتے ہیں کہ اس کا بدترین صورت حال کا تناسب کم از کم ہے۔ درجہ بند کارڈینالٹی کی رکاوٹیں کارڈینالٹی کی رکاوٹوں کی ایک اور عمومی شکل مندرجہ ذیل ہے۔ ان پٹ آئٹمز کو کے زمروں میں تقسیم کیا گیا ہے۔ ہر زمرہ ایچ کے لیے، صلاحیت کی ایک رکاوٹ ہے۔ m ذیلی سیٹوں میں سے ہر ایک زمرہ h سے زیادہ سے زیادہ کے ایچ آئٹمز پر مشتمل ہو سکتا ہے۔ دوسرے لفظوں میں: تمام m ذیلی سیٹوں کو ایک مخصوص پارٹیشن میٹرائڈ کا آزاد سیٹ ہونا چاہیے۔ اس مسئلے کے دو خاص معاملات کا مطالعہ کیا گیا ہے۔ دانا کی متوازن تقسیم کے مسئلے میں، کچھ m پہلے سے متعین آئٹمز دانے ہوتے ہیں، اور m ذیلی سیٹوں میں سے ہر ایک میں ایک دانا (اور غیر دانے کی لامحدود تعداد) ہونا ضروری ہے۔ یہاں، دو زمرے ہیں: صلاحیت 1 کے ساتھ دانا زمرہ، اور لامحدود صلاحیت کے ساتھ غیر دانا زمرہ۔ چن، ہی اور یاؤ ثابت کرتے ہیں کہ مسئلہ NP-سخت ہے یہاں تک کہ k = 3 کے لیے بھی (k = 2 کے لیے اسے زیادہ سے زیادہ وزن کا ملاپ ڈھونڈ کر مؤثر طریقے سے حل کیا جا سکتا ہے)۔ اس کے بعد وہ ایک الگورتھم پیش کرتے ہیں جسے کرنل-ایل پی ٹی (کے ایل پی ٹی) کہا جاتا ہے: یہ ہر سب سیٹ کو ایک کرنل تفویض کرتا ہے، اور پھر ترمیم شدہ ایل پی ٹی الگورتھم چلاتا ہے (ہر آئٹم کو سب سیٹ میں ان میں سے سب سے چھوٹی رقم کے ساتھ رکھتا ہے جن میں کے آئٹمز سے کم ہیں)۔ وہ ثابت کرتے ہیں کہ، k = 3 کے ساتھ، KLPT کا کم از کم سب سے بڑی رقم کا تخمینہ تناسب ہے۔ تاہم، چن، ہی اور لن کا دعوی ہے کہ اس کا سخت تخمینہ تناسب کم از کم سب سے بڑی رقم اور زیادہ سے زیادہ سب سے چھوٹی رقم کے لیے ہے۔ ایک فی زمرہ تقسیم اس مسئلے کی ایک اور قسم میں، سائز m کے کچھ k زمرے ہیں، اور ہر ذیلی سیٹ میں ہر زمرے سے بالکل ایک آئٹم ہونا چاہیے۔ یعنی ہر زمرے کے لیے کے ایچ = 1۔ وو اور یاؤ نے پرتوں والا ایل پی ٹی الگورتھم پیش کیا-جو ایل پی ٹی الگورتھم کا ایک متغیر ہے۔ وہ ثابت کرتے ہیں کہ اس کا تخمینہ تناسب سب سے بڑی رقم کو کم کرنے کے لیے ہے ؛ عام صورت میں سب سے چھوٹی رقم کو زیادہ سے زیادہ کرنے کے لیے ؛ اور کچھ خاص صورتوں میں، عام k اور k = 3 کے لیے بہتر کیا جا سکتا ہے۔ لی اور لی نے ایک ہی مسئلے کے لیے مختلف الگورتھم پیش کیے۔ سب سے بڑی رقم کو کم کرنے کے لیے، وہ مستقل k کے لیے ایک EPTAS، اور مستقل m کے لیے FPTAS پیش کرتے ہیں۔ سب سے چھوٹی رقم کو زیادہ سے زیادہ کرنے کے لیے، وہ عام صورت کے لیے 1/(k−1) تخمینہ الگورتھم، اور مستقل k کے لیے ایک EPTAS پیش کرتے ہیں۔ وہ ایک زیادہ عام مقصد کا بھی مطالعہ کرتے ہیں: رقم کے ویکٹر کے lp-نارم کو کم کرنا۔ وہ ثابت کرتے ہیں کہ پرت دار-ایل پی ٹی الگورتھم تمام اصولوں کے لیے 2-ضمیمہ الگورتھم ہے۔ ڈیل اولمو، ہینسن، پلوٹینو اور اسٹورچی اس مسئلے کے 32 مختلف مقاصد کا مطالعہ کرتے ہیں۔ چار آپریٹرز میں سے ہر ایک کے لیے میکس، منٹ، سم، ڈف، ہر سب سیٹ کے اندر کے آئٹمز پر ایک آپریٹر لگایا جا سکتا ہے، اور پھر مختلف سب سیٹس کے لیے ایم کے نتائج پر ایک آپریٹر لگایا جا سکتا ہے۔ ان 16 مقاصد میں سے ہر ایک کو زیادہ سے زیادہ یا کم سے کم کیا جا سکتا ہے، کل 32 کے لیے۔ وہ دکھاتے ہیں کہ ان میں سے 21 مسائل کو لکیری وقت میں حل کیا جا سکتا ہے۔ 7 کے لیے زیادہ پیچیدہ، لیکن پھر بھی کثیر الجہتی وقت، الگورتھم کی ضرورت ہوتی ہے۔ 3 این پی-سخت ہیں: زیادہ سے زیادہ (کم، مجموعہ)، کم سے کم (زیادہ سے زیادہ، مجموعہ) اور کم سے کم (فرق، مجموعہ)۔ انہوں نے کم سے کم کرنے (فرق، فرق) کی حیثیت کو کھلا چھوڑ دیا۔ یہ بھی دیکھیں کہ میٹرائڈ سے محدود نمبر پارٹیشننگ ایک عمومی شکل ہے جس میں ایک فکسڈ میٹرائڈ کو پیرامیٹر کے طور پر دیا جاتا ہے، اور ہر ایک ایم سبسیٹ اس میٹرائڈ کا ایک آزاد سیٹ یا بیس ہونا چاہیے۔ کارڈینیلیٹی کی رکاوٹیں میٹرائڈ کی رکاوٹوں کے خاص معاملات ہیں جن میں میٹرائڈ ایک یکساں میٹرائڈ ہوتا ہے۔ درجہ بند کارڈینالٹی کی رکاوٹیں ایک خاص معاملہ ہے جس میں میٹرائڈ ایک پارٹیشن میٹرائڈ ہے۔ حوالہ جات نمبر پارٹیشننگ