Matroid-constrained number partitioning
میٹرائڈ سے محدود نمبر پارٹیشننگ ملٹی وے نمبر پارٹیشننگ کے مسئلے کی ایک قسم ہے، جس میں پارٹیشن میں ذیلی سیٹ میٹرائڈ کے آزاد سیٹ ہونے چاہئیں۔ اس مسئلے کا ان پٹ آئٹمز کا ایک سیٹ S، ایک مثبت عدد m، اور اسی سیٹ S پر کچھ m میٹرائڈز ہے۔ مقصد S کو m سبسیٹس میں تقسیم کرنا ہے، جیسے کہ ہر سبسیٹ i میٹرائڈ i میں ایک آزاد سیٹ ہو۔ اس رکاوٹ کے تابع، کچھ معروضی فنکشن کو کم سے کم کیا جانا چاہیے، مثال کے طور پر، ذیلی سیٹ میں سب سے بڑی رقم آئٹم کے سائز کو کم سے کم کرنا۔ زیادہ عام قسم میں، ایم میٹروئڈز میں سے ہر ایک کا وزن فنکشن ہوتا ہے، جو گراؤنڈ سیٹ کے ہر عنصر کو وزن تفویض کرتا ہے۔ مختلف معروضی افعال پر غور کیا گیا ہے۔ تین آپریٹرز میں سے ہر ایک کے لیے زیادہ سے زیادہ، کم سے کم، رقم، کوئی بھی اس آپریٹر کو ہر ذیلی سیٹ میں آئٹمز کے وزن پر، اور خود ذیلی سیٹ پر استعمال کر سکتا ہے۔ مجموعی طور پر، 9 ممکنہ معروضی افعال ہیں، جن میں سے ہر ایک کو زیادہ سے زیادہ یا کم سے کم کیا جا سکتا ہے۔ خصوصی معاملات میٹرائڈ پابند تقسیم کے مسائل کے کچھ اہم خصوصی معاملات یہ ہیں: (زیادہ سے زیادہ، مجموعہ) مقصد ذیلی سیٹ میں کل وزن کے تمام ذیلی سیٹوں پر زیادہ سے زیادہ ہے۔ جب اشیاء ملازمتوں کی نمائندگی کرتی ہیں اور وزن ان کی لمبائی کی نمائندگی کرتے ہیں، تو یہ مقصد محض شیڈول کا میک اسپین ہوتا ہے۔ لہذا، اس مقصد کو کم سے کم کرنا میٹرائڈ رکاوٹوں کے تحت میک اسپین کو کم کرنے کے مترادف ہے۔ اس تناظر میں زیادہ سے زیادہ (کم از کم، رقم) کے دوہرے مقصد کا بھی مطالعہ کیا گیا ہے۔ وہ خاص معاملہ جس میں میٹرائڈز فری میٹرائڈز ہوتے ہیں (کوئی رکاوٹ نہیں) اور ایم وزن کے افعال ایک جیسے ہوتے ہیں، یکساں مشینوں کے شیڈولنگ سے مطابقت رکھتے ہیں، جسے ملٹی وے نمبر پارٹیشننگ بھی کہا جاتا ہے۔ مفت میٹروئڈز اور مختلف وزن کے افعال کا معاملہ غیر متعلقہ مشینوں کے شیڈولنگ سے مطابقت رکھتا ہے۔ یکساں میٹروئڈز کا خاص معاملہ ذیلی سیٹوں پر کارڈینالیٹی کی رکاوٹوں سے مطابقت رکھتا ہے۔ پارٹیشن میٹروئڈز کا زیادہ عام معاملہ درجہ بند کارڈینالیٹی رکاوٹوں سے مطابقت رکھتا ہے۔ ان مسائل کو متوازن نمبر پارٹیشننگ کے صفحہ میں بیان کیا گیا ہے۔ (مجموعہ، مجموعہ) مقصد تمام ذیلی سیٹوں میں تمام آئٹمز کے وزن کا مجموعہ ہے، جہاں ہر ذیلی سیٹ میں وزن کا حساب میٹرائڈ i کے وزن کے فعل سے لگایا جاتا ہے۔ اس مقصد کو کم سے کم کرنے کو وزن والے میٹروئڈ چوراہے کے مسئلے تک کم کیا جا سکتا ہے-زیادہ سے زیادہ وزن والے ذیلی سیٹ کو تلاش کرنا جو بیک وقت دو میٹروئڈز میں آزاد ہو۔ یہ مسئلہ کثیر الجہتی وقت میں حل کرنے کے قابل ہے۔ (زیادہ سے زیادہ، زیادہ سے زیادہ) مقصد تمام ذیلی سیٹوں میں زیادہ سے زیادہ وزن ہے، جہاں ہر ذیلی سیٹ میں وزن کا حساب میٹرائڈ i کے وزن کے فعل سے لگایا جاتا ہے۔ گرافک میٹروئڈز کے ساتھ اس مقصد کو کم سے کم کرنے کا استعمال کم سے کم رکاوٹ پھیلے ہوئے درخت کے مسئلے کو حل کرنے کے لیے کیا جا سکتا ہے۔ (مجموعہ، کم از کم) مقصد تمام ذیلی سیٹوں میں کم از کم وزن کا مجموعہ ہے۔ اس مقصد کو زیادہ سے زیادہ کرنا، k یکساں گرافیکل میٹروئڈز کے ساتھ، ٹری پارٹیشن کے مسئلے پر محیط زیادہ سے زیادہ کل صلاحیت کو حل کرنے کے لیے استعمال کیا جا سکتا ہے۔ (مجموعہ، زیادہ سے زیادہ) مقصد تمام ذیلی سیٹوں میں زیادہ سے زیادہ وزن کا مجموعہ ہے۔ یہ مقصد شیڈولنگ کے لیے درکار کل میموری کی نمائندگی کر سکتا ہے، جب ہر میٹرائڈ i مشین i میں قابل عمل مختص کی نمائندگی کرتا ہے۔ عام میٹرائڈ رکاوٹوں پر سب سے پہلے برکارڈ اور یاؤ نے غور کیا۔ انہوں نے دکھایا کہ میٹروئڈز کے ذیلی طبقے کے لیے لالچی الگورتھم کے ذریعے کثیر الجہتی وقت میں کم سے کم (مجموعہ، زیادہ سے زیادہ) کیا جا سکتا ہے، جس میں پارٹیشن میٹروئڈز شامل ہیں۔ ہوانگ اور روتھبلم نے ایک متبادل کافی شرط پیش کی۔ وو اور یاؤ نے عام میٹرائڈ رکاوٹوں کے ساتھ کم سے کم (زیادہ سے زیادہ، مجموعہ) کے لیے ایک تخمینہ الگورتھم پیش کیا۔ عباسی، میرکنی اور ٹھاکر میٹرائڈ رکاوٹوں کے تحت تنوع کو زیادہ سے زیادہ کرنے کے مسئلے کے لیے ایک تخمینہ الگورتھم پیش کرتے ہیں۔ کاوسے، کمورا، ماکینو اور سمیتا دکھاتے ہیں کہ زیادہ سے زیادہ مسائل کو کم سے کم مسائل تک کم کیا جا سکتا ہے۔ پھر، وہ کم سے کم کرنے کے سات مسائل کا تجزیہ کرتے ہیں: کم سے کم کرنا (مجموعہ، زیادہ سے زیادہ): مسئلہ مضبوطی سے این پی سخت ہے یہاں تک کہ جب میٹرائڈز اور وزن ایک جیسے ہوں۔ یکساں میٹرائڈز اور وزن کے لیے پی ٹی اے ایس ہے۔ عام میٹرائڈز اور وزن کے لیے، کسی بھی ε> 0 کے لیے ایک εm-एप्रاکسیمیشن الگورتھم ہے۔ عنصر O (لاگ m) کے ساتھ تخمینہ لگانا NP-مشکل ہے۔ کم سے کم کرنا (کم سے کم، کم سے کم)، (زیادہ سے زیادہ، زیادہ سے زیادہ)، (کم سے کم، زیادہ سے زیادہ) اور (کم سے کم، جمع): کثیر الجہتی وقت کے الگورتھم ہیں۔ وہ مسائل کو میٹرائڈ پارٹیشننگ کے مسئلے کی فزیبلٹی کے مسئلے تک کم کر دیتے ہیں۔ کم سے کم کرنا (زیادہ سے زیادہ، کم سے کم) اور (جمع، کم سے کم): یکساں میٹرائڈز اور وزن کے لیے کثیر الجہتی وقت کے الگورتھم موجود ہیں۔ عام صورت میں، یہ مضبوطی سے این پی-سخت ہے یہاں تک کہ قریب قریب بھی۔ دیگر دو مسائل کا تجزیہ پچھلے کاموں میں کیا گیا تھا: کم سے کم (زیادہ سے زیادہ، مجموعہ) کو مضبوطی سے این پی-ہارڈ (3-پارٹیشن ایک خاص معاملہ ہے) کے طور پر جانا جاتا ہے، اور کم سے کم (مجموعہ، مجموعہ) کو وزن والے میٹرائڈ چوراہے تک کم کیا جا سکتا ہے، جو کہ کثیر الجہتی ہے۔ متعلقہ مسائل میٹرائڈ پارٹیشننگ ایک مختلف مسئلہ ہے، جس میں حصوں کی تعداد m طے نہیں ہے۔ ایک واحد میٹرائڈ ہے، اور اس کا مقصد اس کے عناصر کو آزاد سیٹوں کی سب سے چھوٹی تعداد میں تقسیم کرنا ہے۔ حوالہ جات میٹرائڈ تھیوری نمبر پارٹیشننگ