পলিনোমিয়াল টাইম অ্যাপ্রক্সিমেশন স্কিম
এনপি-কমপ্লিট সমস্যা যেমন ০-১ ন্যাপস্যাক সমস্যা বা সাবসেট সম সমস্যার জন্য কিছু পলিনোমিয়াল টাইম সমাধান খুঁজে পাওয়া যায়। বাস্তব জগতে এই সমস্যাগুলো খুব জনপ্রিয়, তাই এগুলো হ্যান্ডেল করার কিছু উপায় অবশ্যই থাকবে।
পলিনোমিয়াল টাইম অ্যাপ্রক্সিমেশন স্কিম (PTAS) অপ্টিমাইজেশন সমস্যা অনুমান করার জন্য একটি ধরনের অ্যালগরিদম। ০-১ ন্যাপস্যাক সমস্যার জন্য একটি সিউডো-পলিনোমিয়াল সমাধান আছে, কিন্তু মান বড় হলে তা ব্যবহারযোগ্য নয়। তখন PTAS সমাধান দরকার হয়।
গ্রাফ রঙ করা, কি-সেন্টার সমস্যা ইত্যাদি কিছু এনপি-কমপ্লিট সমস্যার কোনো পরিচিত পলিনোমিয়াল টাইম সমাধান নেই। PTAS অ্যালগরিদম অনুমান করতে ব্যবহৃত হয়। এই অ্যালগরিদমগুলো একটি প্যারামিটার ε > 0 নেয় এবং অনুমানের জন্য (1 + ε) ন্যূনতম এবং (1 - ε) সর্বাধিক করে।
উদাহরণ
মান লেন, যদি আমরা একটি ন্যূনতमीকরণ সমস্যা বেছে নিই এবং ε = 0.5 নিই, তবে PTAS ব্যবহার করে সমাধান প্রায় ১.৫ হবে। তাই রানিং টাইম n-এর পরিমাপে পলিনোমিয়াল হতে হবে, কিন্তু ε-এর পরিমাপে এক্সপোনেনশিয়াল হতে পারে।
