Polynomial Time Approximation Scheme (PTAS) คืออะไร?
เราสามารถหาคำตอบในเวลา Polynomial สำหรับปัญหา NP-Complete บางประเภท เช่น ปัญหา 0-1 Knapsack หรือ Subset Sum ซึ่งเป็นปัญหาที่พบบ่อยในโลกความเป็นจริง จึงมีวิธีการจัดการหลายอย่าง
Polynomial Time Approximation Scheme (PTAS) เป็นประเภทหนึ่งของอัลกอริทึมประมาณค่าสำหรับปัญหาการหาค่าเหมาะสม (Optimization Problems) สำหรับปัญหา 0-1 Knapsack มี Pseudo Polynomial Solution อยู่แล้ว แต่เมื่อค่าตัวเลขมีขนาดใหญ่ คำตอบแบบนั้นจะไม่สามารถนำไปใช้ได้จริง จึงจำเป็นต้องใช้ PTAS แทน
ปัญหา NP-complete บางอย่าง เช่น Graph Coloring หรือ K-Center Problem ไม่มีคำตอบในเวลา Polynomial ที่รู้จัก PTAS ถูกนำมาใช้เพื่อประมาณค่าอัลกอริทึมเหล่านี้ อัลกอริทึมเหล่านี้รับพารามิเตอร์ ε > 0 และทำการประมาณค่าด้วยการลดค่าลงเหลือ (1 + ε) สำหรับปัญหา minimization และเพิ่มค่าขึ้นเป็น (1 - ε) สำหรับปัญหา maximization
ตัวอย่าง
สมมติเราเลือกปัญหา minimization และกำหนด ε = 0.5 คำตอบจาก PTAS จะใกล้เคียงกับ 1.5 เท่าของคำตอบที่เหมาะสมที่สุด เวลาการทำงานต้องเป็น Polynomial ตาม n (ขนาดอินพุต) แต่สามารถเป็น Exponential ตาม ε ได้
