সন্নিকট সর্বাধিক-প্রবাহ ন্যূনতম ছেদন উপপাদ্য

সন্নিকট সর্বাধিক-প্রবাহ ন্যূনতম ছেদন উপপাদ্যসমূহ নেটওয়ার্ক প্রবাহ তত্ত্বের একটি গাণিতিক প্রস্তাবনা। এই উপপাদ্যগুলো বহুপণ্য প্রবাহ সমস্যায় সর্বাধিক প্রবাহের হার এবং ন্যূনতম ছেদ এর মধ্যে সম্পর্ক নিয়ে আলোচনা করে। এসব উপপাদ্য চিত্রলেখ বিভাজন ও সম্পর্কিত সমস্যার জন্য সন্নিকট অ্যালগরিদম উন্নয়নে সহায়ক হয়েছে।

বহুপণ্য প্রবাহ সমস্যা

নেটওয়ার্ক প্রবাহ সমস্যায় একটি "পণ্য" বলতে উৎস ও সঙ্কেত নোডের একটি জোড়াকে বোঝায়। বহুপণ্য প্রবাহ সমস্যায় টেমপ্লেট:Math পণ্য থাকে, যেখানে প্রতিটি পণ্যের নিজস্ব উৎস $s_i$​, সঙ্কেত $t_i$​, এবং চাহিদা $D_i$​ নির্ধারিত থাকে। লক্ষ্য হলো প্রতিটি টেমপ্লেট:Mvar-এর জন্য $s_i$​ থেকে $t_i$ পর্যন্ত $D_{\text{i}}$​ একক পণ্য একযোগে পরিবহন করা, এমনভাবে যে কোনো প্রান্ত দিয়ে যাওয়া মোট পণ্যের পরিমাণ প্রান্তটির ক্ষমতার চেয়ে বেশি না হয়। (অপরিচালিত প্রান্তের ক্ষেত্রে উভয় দিকের প্রবাহের যোগফলও প্রান্তটির ক্ষমতা অতিক্রম করতে পারবে না।) বিশেষত, ১-পণ্য (বা একক পণ্য) প্রবাহ সমস্যা সর্বাধিক প্রবাহ সমস্যা নামে পরিচিত। ফোর্ড-ফালকারসন অ্যালগরিদম অনুসারে, একক পণ্য প্রবাহ সমস্যায় সর্বাধিক প্রবাহ এবং ন্যূনতম ছেদন সর্বদা সমান হয়।

সর্বাধিক প্রবাহ এবং ন্যূনতম ছেদন

বহুপণ্য প্রবাহ সমস্যায় সর্বাধিক-প্রবাহ হলো টেমপ্লেট:Mvar-এর সর্বোচ্চ মান, যেখানে টেমপ্লেট:Mvar প্রতিটি পণ্যের পরিবাহিত অংশের একটি সাধারণ ভগ্নাংশ। এর মানে, প্রতিটি টেমপ্লেট:Mvar-এর জন্য $f{D}_{\text{i}}$​ একক পণ্য একই সঙ্গে পরিবহন করা সম্ভব, যাতে কোনো ক্ষমতা সীমা লঙ্ঘিত না হয়। ন্যূনতম ছেদন হলো সকল ছেদের মধ্যে সেই ছেদের অনুপাত $\phi$-এর সর্বনিম্ন মান, যেখানে $\phi$ হলো ছেদের ক্ষমতা ও ছেদের চাহিদার অনুপাত। বহুপণ্য প্রবাহ সমস্যায় সর্বাধিক-প্রবাহ সর্বদা ন্যূনতম ছেদের দ্বারা ঊর্ধ্বসীমাবদ্ধ থাকে।

একসুতো বহুপণ্য প্রবাহ সমস্যা

একসুতো বহুপণ্য প্রবাহ সমস্যায়, প্রতিটি নোডের জন্য একটি পণ্য থাকে এবং প্রতিটি পণ্যের চাহিদা সমান হয়। (সাধারণত, প্রতিটি পণ্যের চাহিদা এক হিসাবে নির্ধারণ করা হয়।) ভিত্তি নেটওয়ার্ক এবং ক্ষমতাগুলি যেকোনোটি হতে পারে।

গুণফল বহুপণ্য প্রবাহ সমস্যা

গুণফল বহুপণ্য প্রবাহ সমস্যায়, চিত্রলেখ $G=(V,E)$-এ প্রতিটি নোড $v\in V$-এর জন্য একটি ঋণাত্মক নয় এমন ওজন থাকে। নোড টেমপ্লেট:Mvar এবং টেমপ্লেট:Mvar-এর মধ্যে পণ্যের চাহিদা হলো নোড টেমপ্লেট:Mvar এবং নোড টেমপ্লেট:Mvar-এর ওজনের গুণফল। একসুতো বহুপণ্য প্রবাহ সমস্যা হলো গুণফল বহুপণ্য প্রবাহ সমস্যার একটি বিশেষ ক্ষেত্র, যেখানে সকল নোড $u\in V$-এর জন্য ওজন ১ নির্ধারিত থাকে।

রৈখিক প্রোগ্রামিংয়ের দ্বৈততা

সাধারণভাবে, একটি চিত্রলেখ টেমপ্লেট:Mvar-এর জন্য বহুপণ্য প্রবাহ সমস্যার ডুয়াল হলো একটি নির্ধারিত পরিমাণ ওজন (যেখানে ওজনকে দূরত্ব হিসেবে বিবেচনা করা যেতে পারে) চিত্রলেখ টেমপ্লেট:Mvar-এর প্রান্তগুলোতে বণ্টনের সমস্যা, যাতে উৎস ও সঙ্কেত জোড়াগুলির মধ্যে সামষ্টিক দূরত্ব সর্বাধিক করা যায়।

ইতিহাস

বহুপণ্য প্রবাহ সমস্যার সর্বাধিক প্রবাহ এবং ন্যূনতম ছেদের সম্পর্ক নিয়ে গবেষণা ফোর্ড এবং ফালকারসনের ১-পণ্য প্রবাহ সমস্যার ফলাফলের পর থেকে ব্যাপক আগ্রহ অর্জন করেছে। হু প্রমাণ করেছেন যে দুটি পণ্যের জন্য সর্বাধিক প্রবাহ এবং ন্যূনতম ছেদ সর্বদা সমান। অকামুরা এবং সিমোর একটি ৪-পণ্য প্রবাহ সমস্যার উদাহরণ দিয়েছেন, যেখানে সর্বাধিক প্রবাহ ৩/৪ এবং ন্যূনতম ছেদ ১। শাহরোখি এবং মাটুলা দেখিয়েছেন যে, যদি প্রবাহ সমস্যার ডুয়াল একটি নির্দিষ্ট ছেদন শর্ত পূরণ করে, তবে একসুতো বহুপণ্য প্রবাহ সমস্যায় সর্বাধিক প্রবাহ এবং ন্যূনতম ছেদ সমান হবে। আরও অনেক গবেষকও একই ধরনের সমস্যায় বাস্তব ফলাফল উপস্থাপন করেছেন।

একটি সাধারণ নেটওয়ার্ক প্রবাহ সমস্যার জন্য, সর্বাধিক প্রবাহ সর্বদা ন্যূনতম ছেদের টেমপ্লেট:Mvarkগুণের মধ্যে থাকে, কারণ প্রতিটি পণ্য আলাদাভাবে অপ্টিমাইজ করা যেতে পারে, প্রতিটি প্রান্তের ক্ষমতার $1/k$ব্যবহার করে। এটি বিশেষ করে অনেক পণ্য থাকলে একটি ভালো ফলাফল নয়।

সন্নিকট সর্বাধিক-প্রবাহ ন্যূনতম ছেদন উপপাদ্য

একসুতো বহুপণ্য প্রবাহ সমস্যার উপপাদ্য

এই দুটি উপপাদ্য প্রথম ১৯৮৮ সালে টম লেইটন এবং সতীশ রাও দ্বারা প্রবর্তিত হয় এবং পরে ১৯৯৯ সালে সম্প্রসারিত হয়। উপপাদ্য ২, উপপাদ্য ১-এর তুলনায় একটি তীক্ষ্ণ সীমানা প্রদান করে।

উপপাদ্য ১। যেকোনো টেমপ্লেট:Mvar এর জন্য, সর্বাধিক-প্রবাহ টেমপ্লেট:Mvar এবং ন্যূনতম ছেদনসহ একটি টেমপ্লেট:Mvar-নোড অভিন্ন বহুপণ্য প্রবাহ সমস্যা রয়েছে $\phi$ যার জন্য $f\le O\left(\frac{\phi }{\log n}\right)$।

উপপাদ্য ২। যেকোনো অভিন্ন বহুপণ্য প্রবাহ সমস্যার জন্য, $\mathrm{\Omega }\left(\frac{\phi }{\log n}\right)\le f\le \phi$, যেখানে টেমপ্লেট:Mvar সর্বাধিক-প্রবাহ এবং $\phi$ একসুতো বহুপণ্য প্রবাহ সমস্যার ন্যূনতম ছেদ।

উপপাদ্য ২ প্রমাণ করতে, সর্বাধিক প্রবাহ এবং ন্যূনতম ছেদ উভয়কেই আলোচনা করা উচিত। সর্বাধিক প্রবাহের জন্য, রৈখিক প্রোগ্রামিংয়ের দ্বৈততা তত্ত্ব থেকে কৌশলগুলি প্রয়োগ করতে হবে। রৈখিক প্রোগ্রামিংয়ের দ্বৈততা তত্ত্ব অনুযায়ী, একটি অপটিমাল দূরত্ব ফাংশন একটি মোট ওজন প্রদান করে যা একসুতো বহুপণ্য প্রবাহ সমস্যার সর্বাধিক প্রবাহের সমান। ন্যূনতম ছেদের জন্য, একটি ৩-ধাপ প্রক্রিয়া অনুসরণ করতে হবে:

ধাপ ১: একসুতো পণ্য প্রবাহ সমস্যার ডুয়ালটি বিবেচনা করুন এবং অপটিমাল সমাধান ব্যবহার করে প্রান্তে দূরত্ব লেবেল সহ একটি চিত্রলেখ সংজ্ঞায়িত করুন।

ধাপ ২: একটি উৎস বা সঙ্কেত থেকে শুরু করে, চিত্রলেখে একটি অঞ্চল বৃদ্ধি করুন যতক্ষণ না একটি ছোট ক্ষমতাসম্পন্ন ছেদন পাওয়া যায়, যা মূল নোডকে তার সঙ্গী থেকে আলাদা করে।

ধাপ ৩: অঞ্চলটি মুছে ফেলুন এবং ধাপ ২ এর প্রক্রিয়া পুনরাবৃত্তি করুন যতক্ষণ না সব নোড প্রক্রিয়া করা না হয়।

গুণফল বহুপণ্য প্রবাহ সমস্যা সাধারণীকরণ

উপপাদ্য ৩। যেকোনো গুণফল বহুপণ্য প্রবাহ সমস্যার জন্য, যেখানে টেমপ্লেট:Mvarটি পণ্য রয়েছে, $\mathrm{\Omega }\left(\frac{\phi }{\log k}\right)\le f\le \phi$, যেখানে টেমপ্লেট:Mvar হলো সর্বাধিক প্রবাহ এবং $\phi$ হলো গুণফল বহুপণ্য প্রবাহ সমস্যার ন্যূনতম ছেদ।

প্রমাণ পদ্ধতি উপপাদ্য ২ এর মতোই, প্রধান পার্থক্য হলো নোডের ওজনকে বিবেচনায় নিতে হবে।

দিকনির্দেশিত বহুপণ্য প্রবাহ সমস্যায় সম্প্রসারণ

একটি দিকনির্দেশিত বহুপণ্য প্রবাহ সমস্যায়, প্রতিটি প্রান্তের একটি দিক থাকে, এবং প্রবাহটি নির্দিষ্ট দিকেই চলতে সীমাবদ্ধ। একটি দিকনির্দেশিত একসুতো বহুপণ্য প্রবাহ সমস্যায়, প্রতিটি দিকনির্দেশিত প্রান্তের জন্য চাহিদা ১ নির্ধারিত থাকে।

উপপাদ্য ৪। যেকোনো দিকনির্দেশিত একসুতো বহুপণ্য প্রবাহ সমস্যার জন্য, যেখানে টেমপ্লেট:Mvarটি নোড রয়েছে, $\mathrm{\Omega }\left(\frac{\phi }{\log n}\right)\le f\le \phi$, যেখানে টেমপ্লেট:Mvar হলো সর্বাধিক প্রবাহ এবং $\phi$ হলো একসুতো বহুপণ্য প্রবাহ সমস্যার ন্যূনতম ছেদ।প্রমাণ পদ্ধতিতে উপপাদ্য ২-এর তুলনায় প্রধান পার্থক্য হলো, এখন প্রান্তের দিকগুলো বিবেচনায় নিতে হবে যখন ধাপ ১-এ দূরত্ব লেবেল সংজ্ঞায়িত করা হয় এবং ধাপ ২-এ অঞ্চলের বৃদ্ধি করার জন্য আরও বিস্তারিত তথ্য পাওয়া যাবে।

একইভাবে, গুণফল বহুপণ্য প্রবাহ সমস্যার জন্য আমাদের নিম্নলিখিত বর্ধিত উপপাদ্য রয়েছে:

উপপাদ্য ৫। যেকোনো দিকনির্দেশিত গুণফল বহুপণ্য প্রবাহ সমস্যার জন্য, যেখানে টেমপ্লেট:Mvarটি পণ্য রয়েছে, $\mathrm{\Omega }\left(\frac{\phi }{\log k}\right)\le f\le \phi$, যেখানে টেমপ্লেট:Mvar সর্বাধিক-প্রবাহ এবং $\phi$ গুণফল বহুপণ্য প্রবাহ সমস্যার দিকনির্দেশিত ন্যূনতম ছেদ।

অনুমান অ্যালগরিদমে প্রয়োগ

উপরোক্ত উপপাদ্যগুলি এনপি-কঠিন সমস্যাগুলির জন্য অনুমান অ্যালগরিদম ডিজাইন করতে অত্যন্ত কার্যকর, যেমন গ্রাফ ভাগ করার সমস্যা এবং এর বিভিন্ন রূপ। নিচে আমরা কয়েকটি উদাহরণ সংক্ষেপে উপস্থাপন করছি, এবং বিস্তারিত ব্যাখ্যা লেইটন এবং রাও (১৯৯৯) এ পাওয়া যাবে।

পাতলা ছেদন

একটি চিত্রলেখ $G=(V,E)$-এর সবচেয়ে পাতলা ছেদন হলো একটি বিভাজন, যার জন্য দুইটি বিভক্ত উপাদানের মধ্যে সংযোগকারী প্রান্তের সংখ্যা এবং উভয় উপাদানের নোডের সংখ্যা গুণফলের অনুপাত সর্বনিম্ন হয়। এটি একটি এনপি-কঠিন সমস্যা, এবং এটি উপপাদ্য ২ ব্যবহার করে $O(\log n)$ গুণফলে অনুমান করা যেতে পারে। এছাড়াও, যদি প্রান্তের ওজন, নোডের ওজন বা দিকনির্দেশিত প্রান্ত থাকে, তবে এটি উপপাদ্য ৩, ৪ এবং ৫ অনুযায়ী $O(\log p)$ গুণফলে অনুমান করা যেতে পারে, যেখানে টেমপ্লেট:Mvar হলো সেই নোডের সংখ্যা যার ওজন শূন্য নয়।

সামঞ্জস্যপূর্ণ ছেদন এবং বিভাজক

কিছু প্রয়োগে, আমরা একটি ছোট ছেদন খুঁজতে চাই যা একটি চিত্রলেখ $G=(V,E)$-কে প্রায় সমান আকারের টুকরোয় বিভক্ত করে। সাধারণত, একটি ছেদনকে b-সমঞ্জস্যপূর্ণ বা টেমপ্লেট:Math-বিভাজক বলা হয় (যেখানে টেমপ্লেট:Math) যদি$b\pi (V)\le \pi (U)\le (1-b)\pi (V)$ যেখানে $\pi (U)$ হলো টেমপ্লেট:Mvar-এ নোডের ওজনের যোগফল। এটি একটি এনপি-কঠিন সমস্যা। এই সমস্যার জন্য একটি অনুমান অ্যালগরিদম ডিজাইন করা হয়েছে এবং মূল ধারণাটি হলো যে, যদি টেমপ্লেট:Mvar-তে একটি টেমপ্লেট:Mvar-সমঞ্জস্যপূর্ণ ছেদন থাকে যার আকার টেমপ্লেট:Mvar, তবে আমরা একটি টেমপ্লেট:Math-সমঞ্জস্যপূর্ণ ছেদন খুঁজে পাবো যার আকার হবে $O\left(\frac{S\log n}{b-b^{\prime }}\right)$ যেকোনো টেমপ্লেট:Mvar-এর জন্য, যেখানে টেমপ্লেট:Math এবং টেমপ্লেট:Math। তারপর আমরা প্রক্রিয়াটি পুনরাবৃত্তি করি এবং শেষপর্যন্ত ফলস্বরূপ পাই যে ছেদনটির প্রান্তগুলোর মোট ওজন সর্বাধিক হবে $O(S\log \frac{n}{b}-b^{\prime })$।

ভিএলএসআই বিন্যাস সমস্যা

ভিএলএসআই সার্কিট ডিজাইনের ক্ষেত্রে ন্যূনতম আকারের একটি বিন্যাস খুঁজে পাওয়া গুরুত্বপূর্ণ। এই ধরনের সমস্যাকে প্রায়শই একটি চিত্রলেখ সন্নিবেশ সমস্যা হিসেবে মডেল করা যায়। এর উদ্দেশ্য হলো এমন একটি সন্নিবেশ খুঁজে বের করা, যার জন্য বিন্যাস ক্ষেত্রফল ন্যূনতম হয়। ন্যূনতম বিন্যাস ক্ষেত্রফল নির্ধারণ করাও একটি এনপি-কঠিন সমস্যা। একটি অনুমান অ্যালগরিদম প্রবর্তিত হয়েছে, এবং এর ফলাফল হলো অপ্টিমালের $O({\log }^{6}n)$।

অগ্রসর সূচক সমস্যা

টেমপ্লেট:Mvar-নোডবিশিষ্ট একটি চিত্রলেখ টেমপ্লেট:Mvar এবং $K_n$​-এর একটি সন্নিবেশ টেমপ্লেট:Mvar-এ প্রদত্ত হলে, চাং এবং তাঁর সহকর্মীরা সন্নিবেশটির অগ্রসর সূচককে সংজ্ঞায়িত করেছেন টেমপ্লেট:Mvar-এর যেকোনো নোড দিয়ে অতিক্রান্ত সর্বাধিক সংখ্যক পথ (যেগুলো $K_n$​-এর একটি প্রান্তের সমতুল্য) হিসেবে। উদ্দেশ্য হলো এমন একটি সন্নিবেশ খুঁজে বের করা, যা অগ্রসর সূচককে ন্যূনতম করে। সন্নিবেশ পদ্ধতি ব্যবহার করে প্রতিটি চিত্রলেখ টেমপ্লেট:Mvar-এর জন্য নোড এবং প্রান্ত অগ্রসর সূচককে $O(\log n)$-গুণের মধ্যে সীমাবদ্ধ রাখা সম্ভব।

সমতল প্রান্ত অপসারণ

ট্রাগউডাস সুষম বিভাজক খোঁজার অনুমান অ্যালগরিদম ব্যবহার করে টেমপ্লেট:Mvar-এর $O((R\log n+\sqrt{nR})\log \frac{n}{R})$ সংখ্যক প্রান্ত খুঁজে বের করেছেন, যেগুলো অপসারণের ফলে একটি সসীম-ডিগ্রিসম্পন্ন চিত্রলেখ টেমপ্লেট:Mvar সমতল হয়ে যায়। এখানে টেমপ্লেট:Mvar হলো টেমপ্লেট:Mvar-কে সমতল করার জন্য অপসারিত প্রান্তের ন্যূনতম সংখ্যা। এখনো এটি একটি উন্মুক্ত প্রশ্ন যে টেমপ্লেট:Mvar-এর জন্য একটি পলিলগ টেমপ্লেট:Mvar-গুণ অপ্টিমাল অনুমান অ্যালগরিদম বিদ্যমান কিনা।