Domination analysis
একটি আনুমানিক অ্যালগরিদমের আধিপত্য বিশ্লেষণ হল এর কার্যকারিতা অনুমান করার একটি উপায়, যা 1997 সালে গ্লোভার এবং পুনেন দ্বারা প্রবর্তিত হয়েছিল। ধ্রুপদী আনুমানিক অনুপাত বিশ্লেষণের বিপরীতে, যা একটি গণনাকৃত সমাধানের সংখ্যাসূচক গুণমানকে একটি সর্বোত্তম সমাধানের সাথে তুলনা করে, আধিপত্য বিশ্লেষণে সমস্ত সম্ভাব্য সমাধানের সাজানো ক্রমে গণনা করা সমাধানের র্যাঙ্ক পরীক্ষা করা জড়িত। বিশ্লেষণের এই শৈলীতে, একটি অ্যালগরিদমের আধিপত্য সংখ্যা বা আধিপত্য সংখ্যা কে বলা হয়, যদি সমস্যার বিভিন্ন সমাধানের জন্য কে-এর একটি উপসেট বিদ্যমান থাকে যার মধ্যে অ্যালগরিদমের আউটপুট সেরা। আধিপত্য বিশ্লেষণ একটি আধিপত্য অনুপাত ব্যবহার করে প্রকাশ করা যেতে পারে, যা সমাধান স্থানের ভগ্নাংশ যা প্রদত্ত সমাধানের চেয়ে ভাল নয়; এই সংখ্যাটি সর্বদা ব্যবধানের মধ্যে থাকে [0,1], বৃহত্তর সংখ্যাগুলি আরও ভাল সমাধান নির্দেশ করে। আধিপত্য বিশ্লেষণ সাধারণত সেই সমস্যাগুলির ক্ষেত্রে প্রয়োগ করা হয় যার জন্য সম্ভাব্য সমাধানের মোট সংখ্যা জানা যায় এবং যার সঠিক সমাধান করা কঠিন। উদাহরণস্বরূপ, ট্রাভেলিং সেলসম্যানের সমস্যায় (এন-1) রয়েছে! উদাহরণস্বরূপ, এন শহরগুলির সঙ্গে একটি সমস্যার সম্ভাব্য সমাধান। যদি কোনও অ্যালগরিদমের আধিপত্য সংখ্যা (এন-1)!-এর কাছাকাছি বা 1-এর কাছাকাছি আধিপত্য অনুপাতের সমতুল্য দেখানো যায়, তবে এটি কম আধিপত্য সংখ্যা সহ একটি অ্যালগরিদমের চেয়ে বেশি পছন্দসই হিসাবে নেওয়া যেতে পারে। যদি ট্র্যাভেলিং সেলসম্যান সমস্যার মতো কোনও সমস্যার সমাধানের জায়গার এলোমেলো নমুনাগুলি দক্ষতার সাথে খুঁজে পাওয়া সম্ভব হয়, তবে একটি এলোমেলো অ্যালগরিদমের পক্ষে এমন একটি সমাধান খুঁজে পাওয়া সহজ যে উচ্চ সম্ভাবনার সাথে উচ্চ আধিপত্য অনুপাত রয়েছেঃ কেবল নমুনাগুলির একটি সেট তৈরি করুন এবং তাদের মধ্যে থেকে সেরা সমাধান নির্বাচন করুন। (দেখুন, উদাহরণস্বরূপ, অরলিন এবং শর্মা।) এখানে বর্ণিত আধিপত্য সংখ্যাকে একটি গ্রাফের আধিপত্য সংখ্যার সাথে বিভ্রান্ত করা উচিত নয়, যা গ্রাফের ক্ষুদ্রতম প্রভাবশালী সেটের শীর্ষগুলির সংখ্যাকে বোঝায়। সম্প্রতি, ক্রমবর্ধমান সংখ্যক নিবন্ধ প্রকাশিত হয়েছে যেখানে হিউরিস্টিক্সের কার্যকারিতা মূল্যায়নের জন্য আধিপত্য বিশ্লেষণ প্রয়োগ করা হয়েছে। এই ধরনের বিশ্লেষণকে ধ্রুপদী আনুমানিক অনুপাত বিশ্লেষণ ঐতিহ্যের সঙ্গে প্রতিযোগিতা হিসাবে দেখা যেতে পারে। এই দুটি পদক্ষেপকে পরিপূরক হিসাবেও দেখা যেতে পারে। পরিচিত ফলাফল এই বিভাগে পরিচিত ফলাফলের একটি প্রযুক্তিগত সমীক্ষা রয়েছে। ভার্টেক্স কভার অপ্রতিরোধ্য। ধরা যাক ε> 0। পি = এনপি ব্যতীত, ভার্টেক্স কভারের জন্য এমন কোনও বহুপদী অ্যালগরিদম নেই যাতে এর আধিপত্য সংখ্যা 3 ((এন-এন)/3) এর চেয়ে বেশি হয়। ন্যাপস্যাক অপ্রতিরোধ্যতা। ধরা যাক ε> 0। পি = এনপি ব্যতীত, ন্যাপস্যাকের জন্য এমন কোনও বহুপদী অ্যালগরিদম নেই যাতে এর আধিপত্য সংখ্যা 2 এর চেয়ে বেশি হয়। সর্বাধিক সন্তোষজনক টিএসপি রেফারেন্স আনুমানিক অ্যালগরিদম