Matroid-constrained number partitioning
ম্যাট্রয়েড-সীমাবদ্ধ নম্বর পার্টিশন হল মাল্টিওয়ে নম্বর পার্টিশন সমস্যার একটি রূপ, যেখানে পার্টিশনের উপসেটগুলি ম্যাট্রয়েডের স্বাধীন সেট হওয়া উচিত। এই সমস্যার ইনপুট হল আইটেমগুলির একটি সেট S, একটি ধনাত্মক পূর্ণসংখ্যা m, এবং একই সেট S-এর উপর কিছু m ম্যাট্রয়েড। লক্ষ্য হল S-কে m উপসেটে বিভক্ত করা, যাতে প্রতিটি উপসেট i ম্যাট্রয়েড i-এর একটি স্বাধীন সেট হয়। এই সীমাবদ্ধতার সাপেক্ষে, কিছু উদ্দেশ্যমূলক ফাংশনকে ন্যূনতম করা উচিত, উদাহরণস্বরূপ, একটি উপসেটে বৃহত্তম সমষ্টি আইটেমের আকারকে ন্যূনতম করা। আরও সাধারণ রূপে, প্রতিটি এম ম্যাট্রয়েডের একটি ওজন ফাংশন রয়েছে, যা গ্রাউন্ড-সেটের প্রতিটি উপাদানকে একটি ওজন বরাদ্দ করে। বিভিন্ন উদ্দেশ্যমূলক কাজ বিবেচনা করা হয়েছে। তিনটি অপারেটরের প্রত্যেকটির জন্য সর্বোচ্চ, ন্যূনতম, যোগফল, প্রতিটি উপসেটে আইটেমগুলির ওজনের উপর এবং উপসেটগুলিতে নিজেরাই এই অপারেটরটি ব্যবহার করতে পারে। সব মিলিয়ে, 9টি সম্ভাব্য উদ্দেশ্যমূলক ফাংশন রয়েছে, যার প্রত্যেকটিকে সর্বাধিক বা ন্যূনতম করা যেতে পারে। বিশেষ ক্ষেত্রে ম্যাট্রয়েড-সীমাবদ্ধ বিভাজন সমস্যার কিছু গুরুত্বপূর্ণ বিশেষ ক্ষেত্রেঃ (সর্বোচ্চ, যোগফল) উদ্দেশ্য হল সমস্ত উপসেটগুলির উপর উপসেটটির মোট ওজনের সর্বাধিক। যখন জিনিসগুলি কাজের প্রতিনিধিত্ব করে এবং ওজনগুলি তাদের দৈর্ঘ্যের প্রতিনিধিত্ব করে, তখন এই উদ্দেশ্যটি কেবল সময়সূচির মেকস্প্যান। অতএব, এই উদ্দেশ্যটি হ্রাস করা ম্যাট্রয়েড সীমাবদ্ধতার অধীনে মেকস্প্যানকে হ্রাস করার সমতুল্য। সর্বাধিককরণের দ্বৈত লক্ষ্য (ন্যূনতম, যোগফল)-ও এই প্রসঙ্গে অধ্যয়ন করা হয়েছে। বিশেষ ক্ষেত্রে যেখানে ম্যাট্রয়েডগুলি মুক্ত ম্যাট্রয়েড (কোনও সীমাবদ্ধতা নেই) এবং এম ওজন-ফাংশনগুলি অভিন্ন-মেশিন সময়সূচীর সাথে সামঞ্জস্যপূর্ণ, যা মাল্টিওয়ে নম্বর পার্টিশনিং নামেও পরিচিত। বিনামূল্যে ম্যাট্রয়েড এবং বিভিন্ন ওজন-ক্রিয়াকলাপের ক্ষেত্রে সম্পর্কহীন-যন্ত্রের সময়সূচীর সাথে সামঞ্জস্যপূর্ণ। ইউনিফর্ম ম্যাট্রয়েডের বিশেষ ক্ষেত্রে উপসেটগুলিতে কার্ডিনালিটি সীমাবদ্ধতার সাথে মিলে যায়। পার্টিশন ম্যাট্রয়েডের আরও সাধারণ ক্ষেত্রে শ্রেণীবদ্ধ কার্ডিনালিটি সীমাবদ্ধতার সাথে মিলে যায়। এই সমস্যাগুলি সুষম সংখ্যা বিভাজনের পৃষ্ঠায় বর্ণনা করা হয়েছে। (যোগফল, যোগফল) উদ্দেশ্য হল সমস্ত উপসেটগুলির সমস্ত আইটেমের ওজনের সমষ্টি, যেখানে প্রতিটি উপসেট i-এর ওজন ম্যাট্রয়েড i-এর ওজন-ফাংশন দ্বারা গণনা করা হয়। এই উদ্দেশ্যকে হ্রাস করে ওজনযুক্ত ম্যাট্রয়েড ছেদ সমস্যায় হ্রাস করা যেতে পারে-একটি সর্বাধিক ওজনের উপসেট খুঁজে বের করা যা একই সাথে দুটি প্রদত্ত ম্যাট্রয়েডে স্বাধীন। এই সমস্যাটি বহুপদী সময়ে সমাধানযোগ্য। (সর্বোচ্চ, সর্বোচ্চ) উদ্দেশ্য হল সমস্ত উপসেটগুলির সর্বাধিক ওজন, যেখানে প্রতিটি উপসেট i-এর ওজন ম্যাট্রয়েড i-এর ওজন-ফাংশন দ্বারা গণনা করা হয়। গ্রাফিক ম্যাট্রয়েডের সাহায্যে এই উদ্দেশ্যকে হ্রাস করে ন্যূনতম বাধা বিস্তৃত গাছের সমস্যা সমাধান করা যেতে পারে। (যোগফল, সর্বনিম্ন) উদ্দেশ্য হল সমস্ত উপসেটগুলিতে ন্যূনতম ওজনের যোগফল। এই উদ্দেশ্যকে সর্বাধিক করে তোলা, k অভিন্ন গ্রাফিকাল ম্যাট্রয়েড দিয়ে, গাছ বিভাজনের সমস্যা জুড়ে সর্বাধিক মোট ক্ষমতা সমাধান করতে ব্যবহার করা যেতে পারে। (যোগফল, সর্বোচ্চ) উদ্দেশ্য হল সমস্ত উপসেটগুলিতে সর্বাধিক ওজনের যোগফল। এই উদ্দেশ্যটি সময়সূচীর জন্য প্রয়োজনীয় মোট স্মৃতির প্রতিনিধিত্ব করতে পারে, যখন প্রতিটি ম্যাট্রয়েড আই মেশিনে সম্ভাব্য বরাদ্দের প্রতিনিধিত্ব করে। সাধারণ ম্যাট্রয়েড সীমাবদ্ধতা সাধারণ ম্যাট্রয়েড সীমাবদ্ধতা প্রথম বারকার্ড এবং ইয়াও দ্বারা বিবেচনা করা হয়েছিল। তারা দেখিয়েছেন যে ম্যাট্রয়েডের একটি উপশ্রেণীর জন্য একটি লোভী অ্যালগরিদম দ্বারা বহুপদী সময়ে মিনিমাইজিং (যোগফল, সর্বোচ্চ) করা যেতে পারে, যার মধ্যে পার্টিশন ম্যাট্রয়েড রয়েছে। হোয়াং এবং রথব্লাম একটি বিকল্প পর্যাপ্ত শর্ত উপস্থাপন করেছিলেন। উ এবং ইয়াও সাধারণ ম্যাট্রয়েড সীমাবদ্ধতার সাথে ন্যূনতম (সর্বোচ্চ, যোগফল) করার জন্য একটি আনুমানিক অ্যালগরিদম উপস্থাপন করেছিলেন। আব্বাসি, মিরোকনি এবং ঠাকুর ম্যাট্রয়েড সীমাবদ্ধতার অধীনে বৈচিত্র্য সর্বাধিককরণের সমস্যার জন্য একটি আনুমানিক অ্যালগরিদম উপস্থাপন করেছেন। কাওয়াসে, কিমুরা, মাকিনো এবং সুমিতা দেখান যে সর্বাধিক সমস্যাগুলি ন্যূনতম সমস্যাগুলিতে হ্রাস করা যেতে পারে। তারপরে, তারা সাতটি মিনিমাইজেশন সমস্যা বিশ্লেষণ করেঃ মিনিমাইজিং (যোগফল, সর্বোচ্চ): ম্যাট্রয়েড এবং ওজন অভিন্ন হলেও সমস্যাটি দৃঢ়ভাবে এনপি-হার্ড। অভিন্ন ম্যাট্রয়েড এবং ওজনের জন্য একটি পিটিএএস রয়েছে। সাধারণ ম্যাট্রয়েড এবং ওজনের জন্য, যে কোনও ε> 0-এর জন্য একটি εm-অ্যাপ্রোক্সিমেশন অ্যালগরিদম রয়েছে। এটি এনপি-হার্ড থেকে ফ্যাক্টর ও (লগ এম)-এর সাথে আনুমানিক। ন্যূনতমকরণ (ন্যূনতম, ন্যূনতম), (সর্বাধিক, সর্বাধিক), (ন্যূনতম, সর্বাধিক) এবং (ন্যূনতম, যোগফল): বহুপদী-সময়ের অ্যালগরিদম রয়েছে। তারা ম্যাট্রয়েড পার্টিশন সমস্যার সম্ভাব্যতা সমস্যার সমস্যাগুলিকে হ্রাস করে। ন্যূনতমকরণ (সর্বোচ্চ, ন্যূনতম) এবং (সমষ্টি, ন্যূনতম): অভিন্ন ম্যাট্রয়েড এবং ওজনের জন্য বহুপদী-সময় অ্যালগরিদম রয়েছে। সাধারণ ক্ষেত্রে, এটি দৃঢ়ভাবে এনপি-হার্ড এমনকি আনুমানিক। অন্যান্য দুটি সমস্যা পূর্ববর্তী কাজগুলিতে বিশ্লেষণ করা হয়েছিলঃ মিনিমাইজিং (সর্বোচ্চ, যোগফল) দৃঢ়ভাবে এনপি-হার্ড হিসাবে পরিচিত (3-পার্টিশন একটি বিশেষ ক্ষেত্রে), এবং মিনিমাইজিং (যোগফল, যোগফল) ওজনযুক্ত ম্যাট্রয়েড ছেদকে হ্রাস করা যেতে পারে, যা বহুপদী। ম্যাট্রয়েড পার্টিশন সম্পর্কিত সমস্যাগুলি একটি ভিন্ন সমস্যা, যেখানে m অংশের সংখ্যা স্থির করা হয় না। একটি একক ম্যাট্রয়েড রয়েছে এবং এর লক্ষ্য হল এর উপাদানগুলিকে ক্ষুদ্রতম সংখ্যক স্বাধীন সেটে বিভক্ত করা। তথ্যসূত্র ম্যাট্রয়েড তত্ত্ব সংখ্যা বিভাজন