বহুপদী সময় আনুমানিক স্কিম

পলিনোমিয়াল টাইম অ্যাপ্রোক্সিমেশন স্কিম

আমরা NP-সম্পূর্ণ সমস্যার জন্য কিছু বহুপদী সময়ের সমাধান খুঁজে পেতে পারি যেমন 0-1 Knapsack সমস্যা বা উপসেট সমষ্টি সমস্যা। এই সমস্যাগুলি বাস্তব জগতে খুব জনপ্রিয়, তাই এই সমস্যাগুলি পরিচালনা করার কিছু উপায় থাকতে হবে৷

পলিনোমিয়াল টাইম অ্যাপ্রোক্সিমেশন স্কিম (PTAS) হল অপ্টিমাইজেশান সমস্যার জন্য আনুমানিক অ্যালগরিদমের এক প্রকার। 0-1 Knapsack সমস্যার জন্য, একটি Pseudo Polynomial Solution আছে, কিন্তু যখন মানগুলি বড় হয়, তখন সমাধানটি সম্ভব হয় না। তারপর আমাদের একটি PTAS সমাধান দরকার৷

কিছু ​​এনপি-সম্পূর্ণ সমস্যা যেমন গ্রাফ কালারিং, কে-সেন্টার সমস্যা ইত্যাদি। তাদের কোনো বহুপদী সময়ের সমাধান নেই। PTAS অ্যালগরিদম আনুমানিক ব্যবহৃত. এই অ্যালগরিদমগুলি একটি প্যারামিটার ε> 0 নেয় এবং আনুমানিকভাবে আমরা (1 + ε) এবং সর্বাধিক (1 - ε) করব৷

উদাহরণ

উদাহরণ হিসাবে, যদি আমরা একটি মিনিমাইজেশন সমস্যা বেছে নিই এবং ε =0.5 নিই, তাহলে PTAS ব্যবহার করে সমাধান প্রায় 1.5। তাই চলমান সময় অবশ্যই n এর পরিপ্রেক্ষিতে বহুপদী হতে হবে, তবে এটি ε এর পরিপ্রেক্ষিতে সূচকীয় হতে পারে।