A unified and powerful approach is

A unified and powerful approach is presented for devising polynomial approximation schemes
for many strongly NP-complete problems. Such schemes consist of families of approximation algorithms
for each desired performance bound on the relative error c > 0, with running time that is polynomial
when c is fixed. Thougb the polynomiality of these algorithms depends on the degree of approximation
e being fixed, they cannot be improved, owing to a negative result stating that there are no fully
polynomial approximation schemes for strongly NP-complete problems unless NP = P.
The unified technique that is introduced here, referred to as the shifting strategy, is applicable to
numerous geometric covering and packing problems. The method of using the technique and how it
varies with problem parameters are illustrated. A similar technique, independently devised by B. S.
Baker, was shown to be applicable for covering and packing problems on planar graphs.

ผลลัพธ์ (ไทย) 1:

วิธีที่มีประสิทธิภาพ และรวมการนำเสนอการทบทวนแผนงานประมาณพหุนามสำหรับปัญหามากมายขอทำ NP แผนงานดังกล่าวประกอบด้วยครอบครัวของอัลกอริทึมประมาณผลการปฏิบัติงานแต่ละต้องผูกกับข้อผิดพลาดสัมพัทธ์ c > 0 มีการเรียกใช้เวลาที่เป็นพหุนามเมื่อ c เป็นถาวร Thougb polynomiality ของอัลกอริทึมเหล่านี้ขึ้นอยู่กับระดับของการประมาณe ถูกถาวร พวกเขาไม่สามารถปรับปรุงได้ เนื่องจากระบุว่า มีไม่ครบผลลบประมาณพหุนามแบบแผนชุดปัญหาทำ NP ขอเว้น NP =พีเทคนิคการรวมที่เป็นที่รู้จักที่นี่ เรียกว่าเป็นกลยุทธ์ที่เลื่อนลอย เป็นจำนวนมากทรงเรขาคณิตครอบคลุม และบันทึกปัญหา วิธีการใช้เทคนิค และวิธีนั้นมีปัญหาจะแสดงพารามิเตอร์แตกต่างกันไป เทคนิคที่คล้ายกัน คิดค้นอย่างอิสระ โดย B. S.เบเกอร์ ที่แสดงจะใช้ได้ครอบคลุม และบันทึกปัญหาบนระนาบกราฟ

ผลลัพธ์ (ไทย) 2:

วิธีการแบบครบวงจรและมีประสิทธิภาพที่จะนำเสนอสำหรับแผนการณ์ประมาณพหุนาม
สำหรับหลาย ๆ คนอย่างยิ่งปัญหาเอ็นพีบริบูรณ์ แผนดังกล่าวประกอบด้วยครอบครัวของขั้นตอนวิธีการประมาณ
สำหรับการทำงานในแต่ละที่ต้องการผูกพันในความผิดพลาดค> 0 เวลากับการทำงานที่เป็นพหุนาม
เมื่อคได้รับการแก้ไข Thougb polynomiality ของขั้นตอนวิธีเหล่านี้ขึ้นอยู่กับระดับของการประมาณ
อีถูกคงที่พวกเขาไม่สามารถจะดีขึ้นเนื่องจากผลลบที่ระบุว่าไม่มีอย่างเต็มที่
พหุนามแผนการประมาณอย่างยิ่งสำหรับปัญหาเอ็นพีบริบูรณ์เว้นแต่ NP = พี
เทคนิคแบบครบวงจรที่ เป็นที่รู้จักที่นี่เรียกว่ากลยุทธ์การขยับเป็นที่ใช้บังคับกับ
ครอบคลุมเรขาคณิตจำนวนมากและปัญหาการบรรจุ วิธีการใช้เทคนิคและวิธีการที่
แตกต่างกันไปด้วยพารามิเตอร์ปัญหาจะแสดง เทคนิคที่คล้ายกันวางแผนอย่างอิสระโดย BS
เบเกอร์ได้รับการแสดงที่จะมีผลบังคับใช้ครอบคลุมและการบรรจุปัญหาในกราฟระนาบ

ผลลัพธ์ (ไทย) 3:

วิธีการรวมและมีประสิทธิภาพที่นำเสนอสำหรับการพหุนามแบบประมาณ
หลายอย่างมาก ปัญหา NP สมบูรณ์ โครงการดังกล่าว ประกอบด้วย ครอบครัวของขั้นตอนวิธีประมาณ
แต่ละที่ต้องการประสิทธิภาพผูกพันอยู่กับความผิดพลาดสัมพัทธ์ c > 0 มีเวลาวิ่งที่เป็นพหุนาม
เมื่อ C เป็นถาวร thougb ที่ polynomiality ขั้นตอนวิธีเหล่านี้จะขึ้นอยู่กับระดับของการประมาณ
และการแก้ไข พวกเขาไม่สามารถจะดีขึ้นเนื่องจากผลเชิงลบ โดยระบุว่ามีไม่เต็มที่
พหุนามประมาณโครงการอย่างยิ่ง ปัญหา NP สมบูรณ์ เว้นแต่ NP = P
รวมเทคนิคที่แนะนำที่นี่ เรียกว่าเปลี่ยนกลยุทธ์ ใช้ได้

หลายเรขาคณิตครอบคลุมและบรรจุปัญหา วิธีการของการใช้เทคนิคและวิธีการ
ขึ้นอยู่กับพารามิเตอร์ปัญหา เป็นภาพประกอบ เทคนิคที่คล้ายกันอิสระ devised โดย B . S .
เบเกอร์ ถูกแสดงเพื่อให้เหมาะสมสำหรับการครอบคลุมและบรรจุปัญหากราฟระนาบ .