Balanced number partitioning
ব্যালেন্সড নম্বর পার্টিশনিং হল মাল্টিওয়ে নম্বর পার্টিশনিং-এর একটি রূপ যেখানে প্রতিটি সেটে বরাদ্দকৃত আইটেমের সংখ্যার উপর সীমাবদ্ধতা রয়েছে। সমস্যার ইনপুট হল বিভিন্ন মাপের n আইটেমগুলির একটি সেট, এবং দুটি পূর্ণসংখ্যা m, k। আউটপুট হল m উপসেটগুলিতে আইটেমগুলির একটি বিভাজন, যাতে প্রতিটি উপসেটে আইটেমগুলির সংখ্যা সর্বাধিক k হয়। এটি সাপেক্ষে, m উপসেটগুলিতে আকারের যোগফল যতটা সম্ভব একই হওয়া প্রয়োজন। একটি উদাহরণ অ্যাপ্লিকেশন হল অভিন্ন-মেশিনের সময়সূচী যেখানে প্রতিটি মেশিনের একটি জব-কিউ থাকে যা সর্বাধিক কে কাজ ধরে রাখতে পারে। ভি. এল. এস. আই চিপ তৈরির ক্ষেত্রে এবং নমনীয় উৎপাদন ব্যবস্থায় যন্ত্রগুলিকে সরঞ্জাম বরাদ্দ করার ক্ষেত্রেও এই সমস্যার প্রয়োগ রয়েছে। সর্বোত্তম কাজের সময়সূচী সংক্রান্ত সমস্যার জন্য আদর্শ তিন-ক্ষেত্রের স্বরলিপিতে, বৃহত্তম যোগফলকে ন্যূনতম করার সমস্যাকে কখনও কখনও "পি। #≤ কে। সিএমএক্স" দ্বারা চিহ্নিত করা হয়। মধ্যবর্তী ক্ষেত্র "#≤ k" বোঝায় যে প্রতিটি মেশিনে কাজের সংখ্যা সর্বাধিক k হওয়া উচিত। এটি অনিয়ন্ত্রিত সংস্করণের বিপরীতে, যা "দ্বারা চিহ্নিত করা হয়। দ্বিমুখী ভারসাম্যপূর্ণ বিভাজন একটি সাধারণ বিশেষ ক্ষেত্রে দ্বিমুখী ভারসাম্যপূর্ণ বিভাজন বলা হয় যখন দুটি উপসেট (এম = 2) থাকা উচিত। দুটি উপসেটে মেঝে (এন/2) এবং সিলিং (এন/2) আইটেম থাকা উচিত। এটি পার্টিশন সমস্যার একটি রূপ। দুটি উপসেটের যোগফল সমান এমন কোনও বিভাজন রয়েছে কিনা তা নির্ধারণ করা এন. পি-কঠিন; সমস্যা [এস. পি12] দেখুন। এমন অনেক অ্যালগরিদম রয়েছে যার লক্ষ্য একটি ভারসাম্যপূর্ণ পার্টিশন খুঁজে বের করা যেখানে যোগফল যতটা সম্ভব প্রায় সমান। কফম্যান, ফ্রেডেরিকসন এবং লুয়েকার এলপিটি অ্যালগরিদমের একটি সীমাবদ্ধ সংস্করণ উপস্থাপন করেছেন (যাকে আরএলপিটি বলা হয়), যেখানে ইনপুটগুলি জোড়ায় বরাদ্দ করা হয়। যখন ইনপুটগুলি অভিন্নভাবে বিতরণ করা হয়, তখন আরএলপিটি-র প্রত্যাশিত বৃহত্তম যোগফল ঠিক হয়। প্রত্যাশিত কাজ-পার্থক্য (বৃহত্তম এবং ক্ষুদ্রতম যোগফলের মধ্যে পার্থক্য) হল। লুয়েকার এলডিএম অ্যালগরিদমের একটি বৈকল্পিক উপস্থাপন করেন (যাকে পেয়ারওয়াইজ ডিফারেন্সিং মেথড (পিডিএম) বলা হয়)। এর প্রত্যাশিত কাজ-পার্থক্য হল। সাই সীমাবদ্ধ বৃহত্তম পার্থক্য (আরএলডি) নামে একটি অ্যালগরিদম উপস্থাপন করেছেন। এর কাজ-পার্থক্য প্রায় নিশ্চিত। ইয়াকির এম = 2-এর জন্য এলডিএম অ্যালগরিদমের একটি সুষম রূপ উপস্থাপন করেন, যাকে বিএলডিএম বলা হয়। এর প্রত্যাশিত কাজ-পার্থক্য হল। মার্টেন্স ভারসাম্যপূর্ণ দ্বিমুখী বিভাজনের জন্য যে কোনও সময় একটি সম্পূর্ণ অ্যালগরিদম উপস্থাপন করে। এটি সম্পূর্ণ-কর্মকার-কার্প অ্যালগরিদমের সাথে বি. এল. ডি. এম অ্যালগরিদমকে একত্রিত করে। ব্যালেন্সড ট্রিপলেট পার্টিশনিং আরেকটি বিশেষ ক্ষেত্রে 3-পার্টিশনিং বলা হয় যখন প্রতিটি উপসেটে আইটেমের সংখ্যা সর্বাধিক 3 (কে = 3) হওয়া উচিত। সমান অঙ্কের এই ধরনের বিভাজনের অস্তিত্ব আছে কিনা তা নির্ধারণ করা ঠিক 3-বিভাজনের সমস্যা, যা দৃঢ়ভাবে এনপি-হার্ড হিসাবে পরিচিত। আনুমানিক অ্যালগরিদম রয়েছে যার লক্ষ্য এমন একটি পার্টিশন খুঁজে বের করা যেখানে যোগফল যতটা সম্ভব প্রায় সমান। কেলারার এবং ওয়োইঞ্জার এলপিটি অ্যালগরিদমকে তিনগুণ বিভাজনের সাথে খাপ খাইয়ে নেন (যেখানে সর্বাধিক 3 * মি আইটেম রয়েছে এবং প্রতিটি উপসেটে সর্বাধিক 3 টি আইটেম থাকা উচিত)। তাদের অ্যালগরিদমকে পরিবর্তিত-এলপিটি বা এমএলপিটি বলা হয়। এটি বড় থেকে ছোট আইটেম অর্ডার করে এবং প্রতিটি আইটেমকে 3 টিরও কম আইটেমযুক্ত বিনগুলির মধ্যে ক্ষুদ্রতম যোগফল সহ বিনটিতে পরিণত করে। তারা দেখায় যে এম. এল. পি. টি অ্যালগরিদম সর্বাধিক সর্বনিম্ন বৃহত্তম যোগফল অর্জন করে, যা একই আনুমানিক অনুপাত যা এল. পি. টি অনিয়ন্ত্রিত সমস্যার জন্য অর্জন করে। এম. এল. পি. টি-র জন্য সীমাটি শক্ত। চেন, হি এবং লিন দেখান যে, একই সমস্যার জন্য, এম. এল. পি. টি কমপক্ষে সর্বোচ্চ ক্ষুদ্রতম যোগফল অর্জন করে, যা আবার একই অনুপাত যা এল. পি. টি অনিয়ন্ত্রিত সমস্যার জন্য অর্জন করে। কেলারার এবং কোটভ একটি ভিন্ন অ্যালগরিদম উপস্থাপন করেছেন (ঠিক 3 * মি আইটেমের ক্ষেত্রে), যা সর্বনিম্ন বৃহত্তম যোগফলের সর্বাধিক অর্জন করে। বৃহত্তর কার্ডিনালিটিগুলির সাথে ভারসাম্যপূর্ণ বিভাজন আরও সাধারণ ক্ষেত্রে, যাকে কে-পার্টিশন বলা হয়, যখন প্রতিটি উপসেটে আইটেমগুলির সংখ্যা সর্বাধিক কে হওয়া উচিত, যেখানে কে যে কোনও ধনাত্মক পূর্ণসংখ্যা হতে পারে। ব্যাবেল, কেলার এবং কোটভ এমন একটি বৈকল্পিক অধ্যয়ন করেন যেখানে কে × এম আইটেম রয়েছে (কিছু পূর্ণসংখ্যা কে-এর জন্য), এবং প্রতিটি এম সেটে অবশ্যই ঠিক কে আইটেম থাকতে হবে। তারা ন্যূনতম বৃহত্তম যোগফল আনুমানিক করার জন্য বেশ কয়েকটি অনুসন্ধানমূলক অ্যালগরিদম উপস্থাপন করেঃ ভাঁজ অ্যালগরিদমঃ এম = 2-এর জন্য সর্বোত্তম, এবং সাধারণভাবে এর মোটামুটি আনুমানিক অনুপাত রয়েছে। এক্সচেঞ্জ অ্যালগরিদমঃ টাইট আনুমানিক অনুপাত। এটি বহুপদী সময়ে চলে কিনা তা জানা যায় না। প্রাথমিক-দ্বৈত অ্যালগরিদম (এলপিটি এবং মাল্টিফিটের সংমিশ্রণ): সর্বাধিক আনুমানিক অনুপাত। যখন m যথেষ্ট বড় হয় তখন এটি k = 4 এর জন্য আঁটসাঁট হয়; সুনির্দিষ্ট নিম্ন সীমা হল)। এটিও অনুমান করা হয় যে পরিবর্তিত-এল. পি. টি-র আনুমানিক অনুপাত রয়েছে। বর্তমানে, এই অনুমান শুধুমাত্র k = 3-এর ক্ষেত্রেই সত্য বলে জানা যায়। কে> 3-এর জন্য, এটি জানা যায় যে এর আনুমানিক অনুপাত সর্বাধিক 2। মিশেলস, কর্স্ট, আর্টস, ভ্যান লিউয়েন এবং স্পিকস্মা এমন একটি বৈকল্পিক অধ্যয়ন করেন যেখানে প্রতিটি এম সেটের মধ্যে সিলিং (এন/মি) বা মেঝে (এন/মি) আইটেম থাকতে হবে (তাই কে = সিলিং (এন/মি))। তারা ভারসাম্যপূর্ণ-এল. ডি. এম (বি. এল. ডি. এম) কে এম = 2 থেকে সাধারণ এম পর্যন্ত প্রসারিত করে। সাধারণীকৃত অ্যালগরিদম সময়ের সাথে চলে। তারা প্রমাণ করে যে, ন্যূনতম বৃহত্তম যোগফলের জন্য এর আনুমানিক অনুপাত k = 3-এর জন্য 4/3, k = 4-এর জন্য 19/12, k = 5-এর জন্য 103/60, k = 6-এর জন্য 643/360 এবং k = 7-এর জন্য 4603/2520। একটি মিশ্র পূর্ণসংখ্যা রৈখিক প্রোগ্রাম সমাধান করে অনুপাতগুলি পাওয়া গেছে। সাধারণভাবে (যে কোনও কে-এর জন্য), আনুমানিক অনুপাত কমপক্ষে এবং সর্বাধিক। 3,4,5,6,7-এর জন্য সঠিক এম. আই. এল. পি ফলাফল নিম্ন সীমার সাথে মিলে যায়। কে> 7-এর জন্য, কোনও সঠিক ফলাফল জানা যায় না, তবে নিম্ন এবং উপরের সীমার মধ্যে পার্থক্য 0.3 শতাংশেরও কম। যখন পরামিতিটি উপসেটগুলির সংখ্যা (মি) হয়, তখন আনুমানিক অনুপাত ঠিক হয়। ঝাং, মৌরাতিডিস এবং পাং দেখান যে বিএলডিএম উচ্চ কাজের পার্থক্য (সর্বোচ্চ এবং সর্বনিম্ন পরিমাণের মধ্যে পার্থক্য) সহ বিভাজন তৈরি করতে পারে, উভয়ই যখন ইনপুটগুলি সমানভাবে বিতরণ করা হয় এবং যখন তাদের বিতরণ তির্যক হয়। তারা দুটি বিকল্প অনুসন্ধানের প্রস্তাব দেয়ঃ এল. আর. এম কাজ-পার্থক্যকে হ্রাস করে বি. এল. ডি. এম-এর কাজ-পার্থক্যের এক তৃতীয়াংশে নামিয়ে আনে যখন বন্টন অভিন্ন হয়; মেল্ড কাজ-পার্থক্যকে হ্রাস করে যখন বন্টন তির্যক হয়। একটি হাইব্রিড অ্যালগরিদম বিএলডিএম, এলআরএম এবং মেল্ডকে একত্রিত করে এবং বিভিন্ন ডেটা বিতরণের সাথে গতিশীলভাবে খাপ খায়। যখন কে স্থির করা হয়, তখন ভারসাম্যপূর্ণ বিভাজনের জন্য হোচবাম এবং স্ময়সের একটি পিটিএএস ব্যবহার করা যেতে পারে। যখন কে ইনপুটের অংশ হয়, তখন বর্তমানে কোনও পিটিএএস জানা যায় না। ডেল 'অ্যামিকো এবং মার্টেলো যখন সমস্ত সেটে আইটেমের সংখ্যা সর্বাধিক কে হয় তখন বৃহত্তম যোগফল হ্রাস করার সমস্যাটি অধ্যয়ন করে। তারা দেখায় যে এই বৈকল্পিকের রৈখিক-প্রোগ্রাম শিথিলকরণের সমান সর্বোত্তম মান রয়েছে যা অনিয়ন্ত্রিত বৈকল্পিকের এলপি শিথিলকরণের সমান। অভিব্যক্তি, যেখানে xi হল বড় থেকে ছোট অর্ডার করা ইনপুট, সর্বোত্তম বৃহত্তম-যোগফলের জন্য একটি নিম্ন সীমা, এবং এর সবচেয়ে খারাপ-কেস অনুপাত উভয় রূপেই 1/2। উন্নত অভিব্যক্তিটির সবচেয়ে খারাপ-কেস অনুপাত রয়েছে অনিয়ন্ত্রিত বৈকল্পিকের ক্ষেত্রে 2/3 এবং সীমাবদ্ধ বৈকল্পিকের ক্ষেত্রে 1/2। অনিয়ন্ত্রিত বৈকল্পিকের জন্য পরিবর্তিত তালিকার সময়সূচীর আনুমানিক অনুপাত 1/2, তবে সীমাবদ্ধ বৈকল্পিকের জন্য এটি 0 (এটি নির্বিচারে খারাপ হতে পারে)। পরিবর্তিত এলপিটি অ্যালগরিদমের আনুমানিক অনুপাত সর্বাধিক 2। তারা আরও দেখায় যে এর নিম্ন সীমার সবচেয়ে খারাপ-কেস পারফরম্যান্স অনুপাত 3/4, এবং তাদের পিডি অ্যালগরিদমের একটি টাইট পারফরম্যান্স অনুপাত 4/3 (যখন এম যথেষ্ট বড় হয়)। তিনি, তান, ঝু এবং ইয়াও ক্ষুদ্রতম যোগফল সর্বাধিক করার সমস্যাটি বিবেচনা করেন। তারা দেখায় যে ফোল্ডিং অ্যালগরিদমের মোটামুটি আনুমানিক অনুপাত রয়েছে। তারা কমপক্ষে সবচেয়ে খারাপ-কেস অনুপাত সহ একটি নতুন অ্যালগরিদম, হারমনিক 1 উপস্থাপন করে। এই দুটি অ্যালগরিদমই অর্ডিনাল-তারা আইটেমগুলিকে তাদের সঠিক মানের পরিবর্তে কেবল তাদের মধ্যে ক্রমের ভিত্তিতে ভাগ করে। তারা প্রমাণ করে যে, যে কোনও অর্ডিনাল অ্যালগরিদমের ক্ষুদ্রতম যোগফলকে সর্বাধিক করার জন্য সর্বাধিক অনুপাত থাকে। এটি নির্দেশ করে যে, হার্মনিক1 উপসর্গহীনভাবে সর্বোত্তম। যে কোনও স্থির k-এর জন্য, যে কোনও অর্ডিনাল অ্যালগরিদমের অনুপাত সমীকরণের সর্বাধিক ক্ষুদ্রতম মূল। যখন k-এর প্রবণতা অসীমের দিকে থাকে, তখন এই উপরের সীমাটি 0-এর কাছাকাছি চলে আসে। ভারসাম্যপূর্ণ এবং অনিয়ন্ত্রিত সমস্যার মধ্যে সম্পর্ক ভারসাম্যপূর্ণ বিভাজন সমস্যা এবং আদর্শ (অনিয়ন্ত্রিত) বিভাজন সমস্যার আনুমানিকতার মধ্যে কিছু সাধারণ সম্পর্ক রয়েছে। বাবেল, কেলারার এবং কোটভ প্রমাণ করেছেন যে অনিয়ন্ত্রিত সর্বোত্তম এবং সীমাবদ্ধ সর্বোত্তমের মধ্যে অনুপাত সর্বাধিক, এবং এটি শক্ত। কেলারার এবং কোটভ প্রমাণ করেছেন যে, k ক্ষমতা এবং আনুমানিক-অনুপাত r (ন্যূনতম বৃহত্তম যোগফলের জন্য) সহ ভারসাম্যপূর্ণ বিভাজনের জন্য প্রতিটি অনুসন্ধানমূলক অনুমান-অনুপাত সহ অনিয়ন্ত্রিত বিভাজনের জন্য একটি অনুসন্ধানমূলক প্রাপ্তির জন্য নিযুক্ত করা যেতে পারে। বিশেষত, ত্রয়ী বিভাজনের জন্য তাদের-অনুমোদন অ্যালগরিদম (কে = 3) আনুমানিক-অনুপাত সহ অনিয়ন্ত্রিত বিভাজনের জন্য একটি অনুসন্ধানমূলক পেতে ব্যবহার করা যেতে পারে। কার্ডিনালিটির বিভিন্ন সীমাবদ্ধতা কার্ডিনালিটির সীমাবদ্ধতাগুলি প্রতিটি উপসেটে একটি ভিন্ন সীমাবদ্ধতার অনুমতি দিয়ে সাধারণীকরণ করা যেতে পারে। এই বৈকল্পিকটি "উন্মুক্ত সমস্যা" বিভাগে চালু করা হয়েছে, যারা কি-পার্টিশন সমস্যা বলে। তিনি, তান, ঝু এবং ইয়াও বিভিন্ন কার্ডিনালিটি সীমাবদ্ধতার সাথে ক্ষুদ্রতম যোগফলকে সর্বাধিক করার জন্য হারমনিক 2 নামে একটি অ্যালগরিদম উপস্থাপন করেন। তারা প্রমাণ করে যে এর সবচেয়ে খারাপ-কেস অনুপাত অন্তত। শ্রেণীবদ্ধ কার্ডিনালিটি সীমাবদ্ধতা কার্ডিনালিটি সীমাবদ্ধতার আরেকটি সাধারণীকরণ নিম্নরূপ। ইনপুট আইটেমগুলি কে বিভাগে বিভক্ত করা হয়। প্রতিটি বিভাগ এইচ-এর জন্য, একটি ক্ষমতার সীমাবদ্ধতা কে. এইচ রয়েছে। প্রতিটি এম উপসেটে এইচ বিভাগ থেকে সর্বাধিক কে. এইচ আইটেম থাকতে পারে। অন্য কথায়ঃ সমস্ত এম উপসেট একটি নির্দিষ্ট পার্টিশন ম্যাট্রয়েডের স্বাধীন সেট হওয়া উচিত। এই সমস্যার দুটি বিশেষ ক্ষেত্রে অধ্যয়ন করা হয়েছে। কার্নেল বিভাজন কার্নেল ভারসাম্য-বিভাজন সমস্যায়, কিছু এম পূর্ব-নির্দিষ্ট আইটেমগুলি কার্নেল, এবং প্রতিটি এম উপসেটে অবশ্যই একটি একক কার্নেল (এবং সীমাহীন সংখ্যক অ-কার্নেল) থাকতে হবে। এখানে দুটি বিভাগ রয়েছেঃ ক্ষমতা 1 সহ কার্নেল বিভাগ এবং সীমাহীন ক্ষমতা সহ অ-কার্নেল বিভাগ। চেন, হি এবং ইয়াও প্রমাণ করেছেন যে সমস্যাটি এনপি-হার্ড এমনকি কে = 3-এর জন্যও (কে = 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টি হল এনপি-হার্ডঃ সর্বাধিককরণ (ন্যূনতম, যোগফল), ন্যূনতমকরণ (সর্বাধিক, যোগফল) এবং ন্যূনতমকরণ (ডিফ, যোগফল)। তারা মিনিমাইজিং স্ট্যাটাস (ডিফ, ডিফ) খোলা রেখেছিল। ম্যাট্রয়েড-সীমাবদ্ধ সংখ্যা বিভাজন একটি সাধারণীকরণ যেখানে একটি নির্দিষ্ট ম্যাট্রয়েডকে একটি পরামিতি হিসাবে দেওয়া হয় এবং প্রতিটি এম উপসেট এই ম্যাট্রয়েডের একটি স্বাধীন সেট বা বেস হওয়া উচিত। কার্ডিনালিটি সীমাবদ্ধতা ম্যাট্রয়েড সীমাবদ্ধতার বিশেষ ক্ষেত্রে যেখানে ম্যাট্রয়েড একটি অভিন্ন ম্যাট্রয়েড। শ্রেণীবদ্ধ কার্ডিনালিটি সীমাবদ্ধতা একটি বিশেষ ক্ষেত্রে যেখানে ম্যাট্রয়েড একটি পার্টিশন ম্যাট্রয়েড। রেফারেন্স সংখ্যা বিভাজন