None of the above problems was repo

None of the above problems was reported to have a bounded error ratio
approximation algorithm. We shall call an algorithm a b-approximation, 6 > 0, for
a certain problem if the error of the value of the solution delivered by the algorithm
divided by the value of the optimal solution does not exceed 6. Obviously, we
would like to identify a &approximation algorithm such that 6 is as small as
possible. In some cases one can specify a family of algorithms such that for each
E > 0 there is an c-approximation algorithm in the family that solves a given
problem instance within relative error 6. Such a family is called an approximation
scheme. The running time of an c-approximation algorithm will increase monotonically
with l/t. If the functional dependence of the running time on the size of
the input and I/C is polynomial, then the scheme is said to be fully polynomial; if,
on the other hand, it is polynomial only in the input size, the scheme is called
polynomial.

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

ไม่มีปัญหาข้างต้นเป็นรายงานที่มีอัตราผิดพลาดกี่อัลกอริทึมประมาณ เราจะเรียกอัลกอริทึมเป็น b-ประมาณ 6 > 0 สำหรับบางปัญหาหากข้อผิดพลาดของค่าของการแก้ปัญหาการจัดส่ง โดยอัลกอริทึมการหาร ด้วยค่าเหมาะสมแก้ไขปัญหาเกิน 6 แน่นอน เราอยากระบุการและขั้นตอนวิธีประมาณที่ 6 เป็นขนาดเป็นไปได้ ในบางกรณี หนึ่งสามารถระบุครอบครัวของอัลกอริทึมดังกล่าวที่แต่ละE > 0 มีอัลกอริทึม c-ประมาณการในครอบครัวที่ช่วยแก้ตัวให้ตัวอย่างปัญหาภายในเกิดข้อผิดพลาดสัมพัทธ์ 6 ครอบครัวดังกล่าวเรียกว่าการประมาณโครงร่าง จะเพิ่มเวลาทำงานของอัลกอริทึมการ c ประมาณ monotonicallyมี l/t ถ้าที่ทำงานพึ่งเวลาทำขนาดของอินพุตและ I / C คือพหุนาม จากแผนงานกล่าวได้ว่า เป็นพหุนามเต็ม ถ้าบนมืออื่น ๆ เป็นพหุนามในขนาดสัญญาณ ชุดรูปแบบคือพหุนาม

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

ไม่มีปัญหาข้างต้นได้รับรายงานว่าจะมีอัตราการผิดพลาดขอบเขต
ขั้นตอนวิธีการประมาณ เราจะเรียกขั้นตอนวิธีการบีบประมาณ 6> 0 สำหรับ
ปัญหาบางอย่างถ้าข้อผิดพลาดของมูลค่าของการแก้ปัญหาการจัดส่งโดยขั้นตอนวิธีการ
หารด้วยค่าของการแก้ปัญหาที่ดีที่สุดไม่เกิน 6 เห็นได้ชัดว่าเรา
ต้องการที่จะ ระบุและขั้นตอนวิธีการประมาณดังกล่าวที่ 6 เป็นขนาดเล็กที่สุดเท่า
ที่เป็นไปได้ ในบางกรณีสามารถระบุหนึ่งในครอบครัวของขั้นตอนวิธีดังกล่าวว่าสำหรับแต่ละ
E> 0 มีขั้นตอนวิธีการประมาณคในครอบครัวที่แก้ให้
ปัญหาภายในเช่นความผิดพลาดดังกล่าว 6. ครอบครัวที่เรียกว่าใกล้เคียงกับ
โครงการ เวลาการทำงานของอัลกอริทึมคจะเพิ่มขึ้นประมาณ monotonically
กับลิตร / ตัน ถ้าการพึ่งพาอาศัยการทำงานของเวลาทำงานอยู่กับขนาดของ
การป้อนข้อมูลและ I / C เป็นพหุนามแล้วโครงการที่จะกล่าวว่าเป็นพหุนามอย่างเต็มที่ ถ้า
ในทางกลับกันมันเป็นพหุนามในขนาดเพียงป้อนข้อมูลโครงการที่เรียกว่า
พหุนาม

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

ไม่มีของปัญหาดังกล่าวมีรายงานว่าจะมีจำกัดข้อผิดพลาดอัตราส่วน
ประมาณขั้นตอนวิธี เราจะเรียกอัลกอริทึม b-approximation 6 > 0 ,
ปัญหาบางอย่างถ้าข้อผิดพลาดของมูลค่าของการแก้ปัญหาการส่งมอบโดยขั้นตอนวิธี
หารด้วยค่าของสารละลายที่เหมาะสมไม่เกิน 6 เห็นได้ชัดว่าเรา
ต้องการระบุ&ประมาณอัลกอริธึมดังกล่าวว่าเป็นขนาดเล็ก
6เป็นไปได้ ในบางกรณีสามารถระบุครอบครัวของขั้นตอนวิธีดังกล่าวแต่ละ
E > 0 มี c-approximation ขั้นตอนวิธีในครอบครัวที่แก้ให้ปัญหาเช่นข้อผิดพลาดสัมพัทธ์
ภายใน 6 ครอบครัวแบบนี้เรียกว่าการ
โครงร่าง เวลาทํางานของ c-approximation ขั้นตอนวิธีจะเพิ่ม monotonically
L / Tถ้าการพึ่งพาการทำงานของเวลา กับขนาดของอินพุตและฉัน /
c เป็นพหุนาม แล้วโครงการจะครบ 6 ถ้า
; บนมืออื่น ๆที่เป็นพหุนามในใส่ขนาดโครงการที่เรียกว่า
โพลิโนเมียล