อัลกอริทึมการประมาณค่า

ในวิทยาการคอมพิวเตอร์และการวิจัยปฏิบัติการอัลกอริทึมการประมาณค่าเป็นอัลกอริทึม ที่มีประสิทธิภาพ ซึ่งค้นหา คำตอบ โดยประมาณสำหรับปัญหาการหา ค่าเหมาะสมที่สุด (โดยเฉพาะ ปัญหา NP-hard ) พร้อมการรับประกันที่พิสูจน์ได้เกี่ยวกับระยะห่างของคำตอบที่ส่งคืนไปยังคำตอบที่เหมาะสมที่สุด^[¹^]อัลกอริทึมการประมาณค่าเกิดขึ้นตามธรรมชาติในสาขาวิทยาการคอมพิวเตอร์เชิงทฤษฎีอันเป็นผลมาจาก สมมติฐาน P ≠ NP ที่เชื่อกันอย่างกว้างขวาง ภายใต้สมมติฐานนี้ ปัญหาการหาค่าเหมาะสมที่สุดจำนวนมากไม่สามารถแก้ไขได้อย่างแม่นยำในเวลาพหุนามดังนั้น สาขาของอัลกอริทึมการประมาณค่าจึงพยายามทำความเข้าใจว่าเป็นไปได้มากน้อยเพียงใดที่จะประมาณคำตอบที่เหมาะสมที่สุดสำหรับปัญหาดังกล่าวในเวลาพหุนาม ในกรณีส่วนใหญ่ การรับประกันของอัลกอริทึมดังกล่าวเป็นการรับประกันแบบคูณที่แสดงเป็นอัตราส่วนการประมาณค่าหรือปัจจัยการประมาณค่า กล่าวคือ คำตอบที่เหมาะสมที่สุดจะรับประกันได้เสมอว่าจะอยู่ภายในปัจจัยการคูณ (ที่กำหนดไว้ล่วงหน้า) ของคำตอบที่ส่งคืน อย่างไรก็ตาม ยังมีอัลกอริทึมการประมาณค่าจำนวนมากที่ให้การรับประกันแบบบวกเกี่ยวกับคุณภาพของคำตอบที่ส่งคืน ตัวอย่างของอัลกอริทึมการประมาณค่าที่มีการรับประกันแบบคูณคืออัลกอริทึม Christofides-Serdyukovสำหรับปัญหาพนักงานขายเดินทาง โดยให้เส้นทางพนักงานขายเดินทางในเมตริกที่มีความยาวไม่เกิน 3/2 เท่าของเส้นทางที่สั้นที่สุดดังกล่าว ตัวอย่างคลาสสิกของอัลกอริทึมการประมาณค่าที่ให้การรับประกันแบบบวกคือการพิสูจน์เชิงสร้างสรรค์ของทฤษฎีบทของ Vizingซึ่งแสดงวิธีการระบายสีขอบของกราฟแบบไม่มีทิศทางด้วยสีไม่เกิน โดยที่คือดีกรีสูงสุดของโหนดใดๆ เนื่องจากขอบทุกเส้นที่เชื่อมต่อกับโหนดที่มีดีกรีสูงสุดจะต้องมีสีที่แตกต่างกัน การพิสูจน์เชิงสร้างสรรค์ของทฤษฎีบทจึงให้อัลกอริทึมเวลาพหุนามที่ใช้สีเพิ่มเติมไม่เกินหนึ่งสีมากกว่าสีขั้นต่ำที่ต้องการ ตัวอย่างที่น่าสนใจของอัลกอริทึมการประมาณค่าที่ให้ทั้งสองอย่างคืออัลกอริทึมการประมาณค่าแบบคลาสสิกของLenstra , ShmoysและTardos ^[²^]สำหรับการจัดตารางเวลาบนเครื่องขนานที่ไม่เกี่ยวข้องกัน $\Delta +1$ $\Delta$

การออกแบบและการวิเคราะห์อัลกอริธึมการประมาณค่าเกี่ยวข้องกับการพิสูจน์ทางคณิตศาสตร์ที่รับรองคุณภาพของโซลูชันที่ส่งคืนในกรณีที่เลวร้ายที่สุด^{[ 1 ]}ซึ่งทำให้แตกต่างจากฮิวริสติกเช่น อัลกอริธึม การอบอ่อนหรืออัลกอริธึมทางพันธุกรรมซึ่งค้นหาโซลูชันที่ดีพอสมควรสำหรับอินพุตบางอย่าง แต่ไม่ได้ให้ข้อบ่งชี้ที่ชัดเจนตั้งแต่เริ่มต้นว่าเมื่อใดอาจจะสำเร็จหรือล้มเหลว

มีความสนใจอย่างกว้างขวางในวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีในการทำความเข้าใจข้อจำกัดที่เราสามารถประมาณค่าปัญหาการเพิ่มประสิทธิภาพที่มีชื่อเสียงบางอย่างได้ดียิ่งขึ้น ตัวอย่างเช่น หนึ่งในคำถามเปิดที่ค้างคามานานในวิทยาศาสตร์คอมพิวเตอร์คือการพิจารณาว่ามีอัลกอริทึมใดที่ทำงานได้ดีกว่าการประมาณค่า 2 เท่าสำหรับปัญหา Steiner Forest โดย Agrawal et al. ^{[ 3 ]}ความปรารถนาที่จะเข้าใจปัญหาการเพิ่มประสิทธิภาพที่ยากจากมุมมองของการประมาณค่าได้นั้นได้รับแรงบันดาลใจจากการค้นพบความเชื่อมโยงทางคณิตศาสตร์ที่น่าประหลาดใจและเทคนิคที่ใช้ได้อย่างกว้างขวางในการออกแบบอัลกอริทึมสำหรับปัญหาการเพิ่มประสิทธิภาพที่ยาก ตัวอย่างหนึ่งที่รู้จักกันดีของอย่างแรกคืออัลกอริทึม Goemans–Williamsonสำหรับการตัดสูงสุดซึ่งแก้ปัญหาทางทฤษฎีกราฟโดยใช้โปรแกรมกึ่งกำหนดที่มาจากระดับแรกของลำดับชั้นผลรวมของกำลังสอง^{[ 4 ]}

การแนะนำ

ตัวอย่างง่ายๆ ของอัลกอริธึมการประมาณค่าคืออัลกอริธึมสำหรับ ปัญหา การครอบคลุมจุดยอดขั้นต่ำโดยมีเป้าหมายคือการเลือกเซตของจุดยอดที่เล็กที่สุดเพื่อให้ขอบทุกขอบในกราฟอินพุตมีจุดยอดที่เลือกอย่างน้อยหนึ่งจุด วิธีหนึ่งในการหาการครอบคลุมจุดยอดคือการทำซ้ำกระบวนการต่อไปนี้: หาขอบที่ยังไม่ถูกครอบคลุม เพิ่มจุดปลายทั้งสองของขอบนั้นลงในการครอบคลุม และลบขอบทั้งหมดที่เชื่อมต่อกับจุดยอดใดจุดหนึ่งออกจากกราฟ เนื่องจากการครอบคลุมจุดยอดใดๆ ของกราฟอินพุตจะต้องใช้จุดยอดที่แตกต่างกันเพื่อครอบคลุมขอบแต่ละขอบที่พิจารณาในกระบวนการ (เนื่องจากมันสร้างการจับคู่ ) ดังนั้นการครอบคลุมจุดยอดที่สร้างขึ้นจึงมีขนาดใหญ่กว่าการครอบคลุมจุดยอดที่เหมาะสมที่สุดไม่เกินสองเท่า กล่าวอีกนัยหนึ่ง นี่คืออัลกอริธึมการประมาณค่าแบบคงที่ที่มีปัจจัยการประมาณค่าเท่ากับ 2 ภายใต้สมมติฐานเกมที่ไม่ซ้ำกัน ล่าสุด ปัจจัยนี้ยังเป็นปัจจัยที่ดีที่สุดที่เป็นไปได้อีกด้วย^{[ 5 ]}

ปัญหา NP-hard มีความหลากหลายอย่างมากในด้านความสามารถในการประมาณค่า บางปัญหา เช่นปัญหาเป้สะพายหลังสามารถประมาณค่าได้ภายในตัวคูณสำหรับค่าคงที่ใดๆและด้วยเหตุนี้จึงสร้างคำตอบที่ใกล้เคียงกับค่าที่เหมาะสมที่สุด (ตระกูลของอัลกอริทึมการประมาณค่าดังกล่าวเรียกว่าแผนการประมาณค่าในเวลาพหุนามหรือ PTAS) ส่วนปัญหาอื่นๆ นั้นเป็นไปไม่ได้ที่จะประมาณค่าได้ภายในค่าคงที่ใดๆ หรือแม้แต่ตัวคูณพหุนาม เว้นแต่ว่าP = NPเช่นในกรณีของปัญหาคลิกสูงสุดดังนั้น ประโยชน์ที่สำคัญอย่างหนึ่งของการศึกษาอัลกอริทึมการประมาณค่าคือการจำแนกความยากของปัญหา NP-hard ต่างๆ ได้อย่างละเอียดกว่าการจำแนกที่ได้จากทฤษฎีความสมบูรณ์ของ NP กล่าว อีกนัยหนึ่ง แม้ว่าปัญหา NP-complete อาจเทียบเท่ากัน (ภายใต้การลดรูปในเวลาพหุนาม) จากมุมมองของคำตอบที่แน่นอน แต่ปัญหาการหาค่าเหมาะสมที่สุดที่สอดคล้องกันนั้นมีพฤติกรรมที่แตกต่างกันมากจากมุมมองของคำตอบโดยประมาณ $1+\epsilon$ $\epsilon >0$

เทคนิคการออกแบบอัลกอริทึม

ปัจจุบันมีเทคนิคที่ได้รับการยอมรับหลายวิธีในการออกแบบอัลกอริธึมประมาณค่า ซึ่งรวมถึงเทคนิคต่อไปนี้

อัลกอริทึมโลภ
การค้นหาในพื้นที่
การแจงนับและการเขียนโปรแกรมเชิงพลวัต (ซึ่งมักใช้สำหรับการประมาณค่าแบบพารามิเตอร์ ด้วย )
เทคนิคการเขียนโปรแกรมทางคณิตศาสตร์ ซึ่งเกี่ยวข้องกับการสร้างแบบจำลองปัญหาที่พิจารณาด้วยสูตรการเขียนโปรแกรมทางคณิตศาสตร์ที่เหมาะสม (โดยทั่วไปคือการเขียนโปรแกรมแบบนูน ) เช่นการเขียนโปรแกรมเชิงเส้นการเขียนโปรแกรมกึ่งกำหนดเชิงบวก เป็นต้น เพื่อให้ได้คำตอบที่ผ่อนคลายสำหรับปัญหา จากนั้นจึงนำเทคนิคเชิงอัลกอริทึมเพิ่มเติมมาใช้กับสูตรเหล่านี้
- วิธีการปัดเศษ วิธีนี้เกี่ยวข้องกับการแก้สมการที่พิจารณาเพื่อให้ได้คำตอบที่เป็นเศษส่วนที่ดี แล้วแปลงเป็นคำตอบที่เป็นจำนวนเต็ม เทคนิคการปัดเศษที่ใช้กันทั่วไป ได้แก่ การปัดเศษแบบเกณฑ์ง่าย การปัดเศษแบบสุ่มการปัดเศษแบบ วน ซ้ำ เป็นต้น
- วิธีการหาคำตอบคู่ขนาน (Dual-fitting methods) คือการตีความอัลกอริธึมเชิงการจัดเรียง (โดยทั่วไปคืออัลกอริธึมแบบโลภ) ที่ตั้งใจไว้ ให้เป็นกระบวนการคำนวณหาคำตอบที่เป็นไปได้สำหรับโปรแกรมคู่ขนานของสูตรที่พิจารณา
- วิธีการแบบคู่ดั้งเดิม
การฝังปัญหาลงในตัวชี้วัดบางอย่าง แล้วแก้ปัญหาโดยใช้ตัวชี้วัดนั้น วิธีนี้เรียกอีกอย่างว่า การฝังตัวชี้วัด (metric embedding)
การสุ่มตัวอย่างและการใช้ความสุ่มโดยทั่วไป ร่วมกับวิธีการข้างต้น

การรับประกันภายหลัง

ในขณะที่อัลกอริธึมการประมาณค่ามักให้การรับประกันกรณีที่เลวร้ายที่สุดล่วงหน้า (ไม่ว่าจะเป็นแบบบวกหรือแบบคูณ) ในบางกรณี อัลกอริธึมยังให้การรับประกันภายหลังซึ่งมักจะดีกว่ามาก กรณีนี้มักเกิดขึ้นกับอัลกอริธึมที่ทำงานโดยการแก้ปัญหาการผ่อนคลายแบบนูนของปัญหาการหาค่าที่เหมาะสมที่สุดบนอินพุตที่กำหนด ตัวอย่างเช่น มีอัลกอริธึมการประมาณค่าที่แตกต่างกันสำหรับการครอบคลุมจุดยอดขั้นต่ำที่แก้ปัญหาการผ่อนคลายการเขียนโปรแกรมเชิงเส้นเพื่อหาการครอบคลุมจุดยอดที่มีค่าไม่เกินสองเท่าของค่าการผ่อนคลาย เนื่องจากค่าของการผ่อนคลายไม่เคยมากกว่าขนาดของการครอบคลุมจุดยอดที่เหมาะสมที่สุด จึงทำให้ได้อัลกอริธึมการประมาณค่า 2 อีกแบบหนึ่ง แม้ว่าจะคล้ายกับการรับประกันล่วงหน้าของอัลกอริธึมการประมาณค่าก่อนหน้านี้ แต่การรับประกันของอัลกอริธึมหลังนั้นอาจดีกว่ามาก (โดยเฉพาะอย่างยิ่งเมื่อค่าของการผ่อนคลายการเขียนโปรแกรมเชิงเส้นอยู่ห่างจากขนาดของการครอบคลุมจุดยอดที่เหมาะสมที่สุด)

ความยากของการประมาณค่า

อัลกอริทึมการประมาณค่าเป็นสาขาการวิจัยที่เกี่ยวข้องอย่างใกล้ชิดและได้รับข้อมูลจากทฤษฎีความไม่สามารถประมาณค่าได้ซึ่งพิสูจน์ได้ว่าไม่มีอัลกอริทึมที่มีประสิทธิภาพที่มีอัตราส่วนการประมาณค่าที่แน่นอน (โดยมีเงื่อนไขตามสมมติฐานที่เชื่อกันอย่างกว้างขวาง เช่น สมมติฐาน P ≠ NP) โดยวิธีการลดทอนในกรณีของปัญหาพนักงานขายเดินทางเมตริก ผลลัพธ์ความไม่สามารถประมาณค่าได้ที่ดีที่สุดที่ทราบกันดีนั้นตัดอัลกอริทึมที่มีอัตราส่วนการประมาณค่าน้อยกว่า 123/122 ≈ 1.008196 ออกไป เว้นแต่ว่า P = NP, Karpinski, Lampis, Schmied ^{[ 6 ]}เมื่อรวมกับความรู้เกี่ยวกับการมีอยู่ของอัลกอริทึมการประมาณค่า 1.5 ของ Christofides สิ่งนี้บอกเราว่าเกณฑ์ของความสามารถในการประมาณค่าสำหรับปัญหาพนักงานขายเดินทางเมตริก (ถ้ามีอยู่จริง) อยู่ระหว่าง 123/122 และ 1.5

แม้ว่าผลลัพธ์ที่ไม่สามารถประมาณค่าได้จะได้รับการพิสูจน์มาตั้งแต่ทศวรรษ 1970 แล้ว แต่ผลลัพธ์ดังกล่าวได้มาด้วยวิธีการเฉพาะกิจ และในขณะนั้นยังไม่มีความเข้าใจอย่างเป็นระบบ จนกระทั่งผลลัพธ์ในปี 1990 ของ Feige, Goldwasser, Lovász, Safra และ Szegedy เกี่ยวกับความไม่สามารถประมาณค่าได้ของIndependent Set ^{[ 7 ]}และทฤษฎีบท PCP ที่มีชื่อเสียง ^{[ 8 ]} จึงได้มีการค้นพบเครื่องมือที่ทันสมัยสำหรับการพิสูจน์ผลลัพธ์ที่ไม่สามารถประมาณค่าได้ ตัวอย่างเช่น ทฤษฎีบทPCP แสดงให้เห็นว่า อัลกอริทึมการประมาณค่า ของ Johnsonในปี 1974 สำหรับMax SAT , set cover , independent setและcoloringทั้งหมดบรรลุอัตราส่วนการประมาณค่าที่เหมาะสมที่สุด โดยสมมติว่า P ≠ NP ^{[ 9 ]}

ความเป็นจริง

ไม่ใช่ว่าอัลกอริธึมการประมาณค่าทั้งหมดจะเหมาะสมกับการใช้งานจริงโดยตรง บางอัลกอริธึมเกี่ยวข้องกับการแก้ปัญหาการเขียนโปรแกรมเชิงเส้นที่ ไม่ซับซ้อน / การผ่อนคลาย แบบกึ่งกำหนด (ซึ่งอาจต้องใช้อัลกอริธึมทรงรี ) โครงสร้างข้อมูลที่ซับซ้อน หรือเทคนิคอัลกอริธึมที่ซับซ้อน ทำให้เกิดปัญหาในการใช้งานที่ยาก หรือประสิทธิภาพเวลาในการทำงานที่ดีขึ้น (เมื่อเทียบกับอัลกอริธึมที่แม่นยำ) เฉพาะกับข้อมูลป้อนเข้าขนาดใหญ่ที่ไม่สามารถนำไปใช้ได้จริงเท่านั้น นอกเหนือจากปัญหาในการใช้งานและเวลาในการทำงานแล้ว การรับประกันที่ได้รับจากอัลกอริธึมการประมาณค่าอาจไม่แข็งแกร่งพอที่จะพิสูจน์ได้ว่าเหมาะสมที่จะนำไปใช้ในทางปฏิบัติ แม้ว่าจะไม่สามารถใช้งานได้ "ทันที" ในการใช้งานจริง แต่แนวคิดและข้อมูลเชิงลึกเบื้องหลังการออกแบบอัลกอริธึมดังกล่าว มักสามารถนำไปประยุกต์ใช้ในรูปแบบอื่นในอัลกอริธึมเชิงปฏิบัติได้ ในลักษณะนี้ การศึกษาอัลกอริธึมที่มีราคาแพงมากจึงไม่ใช่การศึกษาเชิงทฤษฎีอย่างเดียว เพราะสามารถให้ข้อมูลเชิงลึกที่มีคุณค่าได้

ในกรณีอื่นๆ แม้ว่าผลลัพธ์เริ่มต้นจะเป็นเพียงความสนใจทางทฤษฎีเท่านั้น แต่เมื่อเวลาผ่านไป ด้วยความเข้าใจที่ดียิ่งขึ้น อัลกอริทึมอาจได้รับการปรับปรุงให้ใช้งานได้จริงมากขึ้น ตัวอย่างหนึ่งคือ PTAS เริ่มต้นสำหรับEuclidean TSPโดยSanjeev Arora (และโดยอิสระโดยJoseph Mitchell ) ซึ่งมีเวลาการทำงานที่ยาวนานเกินไปสำหรับการประมาณค่า^[¹⁰^]อย่างไรก็ตาม ภายในหนึ่งปี แนวคิดเหล่านี้ได้ถูกรวมเข้ากับอัลกอริทึมที่มีเวลาเกือบเชิงเส้นสำหรับค่าคงที่ใดๆ^[¹¹^] $n^{O(1/\เอปไซลอน )}$ $1+\epsilon$ $O(n\log n)$ $\epsilon >0$

โครงสร้างของอัลกอริธึมการประมาณค่า

โจทย์การหาค่าเหมาะสมที่สุด:

$\Pi :I\times S$

โดยที่เป็นปัญหาการประมาณค่าเซตของข้อมูลนำเข้า และเซตของคำตอบ เราสามารถกำหนดฟังก์ชันต้นทุนได้ดังนี้: $\Pi$ $I$ $S$

$c:S\rightarrow \mathbb {R} ^{+}$

และชุดของแนวทางแก้ไขที่เป็นไปได้:

$\forall i\in I,S(i)={s\in S:i\Pi _{s}}$

การหาทางออกที่ดีที่สุดสำหรับปัญหาการเพิ่มค่าสูงสุดหรือการลดค่าต่ำสุด: $s^{*}$

$s^{*}\in S(i)$ , $c(s^{*})=min/max\ c(S(i))$

เมื่อกำหนดวิธีแก้ปัญหาที่เป็นไปได้โดยที่เราต้องการการรับประกันคุณภาพของวิธีแก้ปัญหา ซึ่งก็คือประสิทธิภาพที่ต้องรับประกัน (ปัจจัยการประมาณค่า) $s\in S(i)$ $s\neq s^{*}$

โดยเฉพาะอย่างยิ่ง เมื่อมีค่า อัลกอริทึมจะมีค่าประมาณ (หรืออัตราส่วนการประมาณ ) เท่ากับถ้าเราจะได้ว่า: $A_{\Pi }(i)\in S_{i}$ $\rho (n)$ $\forall i\in I\ st|i|=n$

สำหรับ ปัญหา การหาค่าต่ำสุด : ซึ่งหมายความว่าผลลัพธ์ที่ได้จากอัลกอริทึมเมื่อหารด้วยผลลัพธ์ที่เหมาะสมที่สุดจะได้อัตราส่วนเท่ากับ; ${\frac {c(A_{\Pi }(i))}{c(s^{*}(i))}}\leq \rho (n)$ $\rho (n)$
สำหรับ ปัญหา การหาค่าสูงสุด : ซึ่งหมายความว่าคำตอบที่เหมาะสมที่สุดหารด้วยคำตอบที่ได้จากอัลกอริทึมจะได้อัตราส่วนเท่ากับ; ${\frac {c(s^{*}(i))}{c(A_{\Pi }(i))}}\leq \rho (n)$ $\rho (n)$

สามารถพิสูจน์ได้ว่าการประมาณค่ามีความแม่นยำ ( การประมาณค่าที่แม่นยำ ) โดยการแสดงให้เห็นว่ามีบางกรณีที่อัลกอริทึมทำงานได้ใกล้เคียงกับขีดจำกัดของการประมาณค่า ซึ่งบ่งชี้ถึงความแม่นยำของขอบเขต ในกรณีนี้ การสร้างอินสแตนซ์อินพุตที่ออกแบบมาเพื่อบังคับให้อัลกอริทึมทำงานในสถานการณ์ที่เลวร้ายที่สุดก็เพียงพอแล้ว

การรับประกันประสิทธิภาพ

สำหรับอัลกอริธึมการประมาณค่าบางอย่าง สามารถพิสูจน์คุณสมบัติบางอย่างเกี่ยวกับการประมาณค่าผลลัพธ์ที่เหมาะสมที่สุดได้ ตัวอย่างเช่นอัลกอริธึมการประมาณ ค่า แบบρ ถูกกำหนดให้เป็นอัลกอริธึมที่พิสูจน์ได้ว่าค่า/ต้นทุนf ( x ) ของคำตอบโดยประมาณA ( x ) สำหรับอินสแตนซ์xจะไม่มากกว่า (หรือน้อยกว่า ขึ้นอยู่กับสถานการณ์) ค่า OPT ของคำตอบที่เหมาะสมที่สุดซึ่งคูณ ด้วยปัจจัย ρ

{\begin{cases}\mathrm {OPT} \leq f(x)\leq \rho \mathrm {OPT} ,\qquad {\mbox{if }}\rho >1;\\\rho \mathrm {OPT} \leq f(x)\leq \mathrm {OPT} ,\qquad {\mbox{if }}\rho <1.\end{กรณี}}

ปัจจัยρเรียกว่าการรับประกันประสิทธิภาพเชิงสัมพัทธ์ อัลกอริทึมการประมาณค่าจะมีประสิทธิภาพเชิงสัมบูรณ์หรือมีข้อผิดพลาดที่จำกัดcหากได้รับการพิสูจน์แล้วสำหรับทุกกรณีxว่า

(\mathrm {OPT} -c)\leq f(x)\leq (\mathrm {OPT} +c)

ในทำนองเดียวกันการรับประกันประสิทธิภาพR ( x,y ) ของคำตอบyสำหรับอินสแตนซ์xจะถูกกำหนดดังนี้

R(x,y)=\max \left({\frac {OPT}{f(y)}},{\frac {f(y)}{OPT}}\right),

โดยที่f ( y ) คือค่า/ต้นทุนของโซลูชันyสำหรับอินสแตนซ์xเห็นได้ชัดว่าการรับประกันประสิทธิภาพจะมากกว่าหรือเท่ากับ 1 และเท่ากับ 1 ก็ต่อเมื่อyเป็นโซลูชันที่เหมาะสมที่สุด หากอัลกอริทึมAรับประกันว่าจะส่งคืนโซลูชันที่มีการรับประกันประสิทธิภาพไม่เกินr ( n ) แล้วAจะถูกเรียกว่าเป็น อัลกอริทึมการประมาณค่า r ( n ) และมีอัตราส่วนการประมาณค่า r ( n )ในทำนองเดียวกัน ปัญหาที่มี อัลกอริทึมการประมาณค่า r ( n ) จะถูกเรียกว่าสามารถประมาณค่าได้ r ( n )หรือมีอัตราส่วนการประมาณค่าr ( n ) ^[¹²^]^[¹³^]

สำหรับปัญหาการหาค่าต่ำสุด การรับประกันสองแบบที่แตกต่างกันให้ผลลัพธ์เดียวกัน และสำหรับปัญหาการหาค่าสูงสุด การรับประกันประสิทธิภาพสัมพัทธ์ของ ρ เทียบเท่ากับการรับประกันประสิทธิภาพของ r ในเอกสารทางวิชาการ ทั้งสองนิยามนี้ใช้กันทั่วไป แต่จะเห็นได้ชัดว่าใช้นิยามใด เนื่องจากสำหรับปัญหาการหาค่าสูงสุด ρ ≤ 1 ในขณะที่ r ≥ 1 $r=\rho ^{-1}$

การรับประกันประสิทธิภาพสัมบูรณ์ ของอัลกอริทึมการประมาณค่าA บางตัว โดยที่xหมายถึงตัวอย่างของปัญหา และคือการรับประกันประสิทธิภาพของAบนx (นั่นคือ ρ สำหรับตัวอย่างปัญหาx ) คือ: $\mathrm {P} _{A}$ $R_{A}(x)$

\mathrm {P} _{A}=\inf\{r\geq 1\mid R_{A}(x)\leq r,\forall x\}.

กล่าวคือ นั่นคือขอบเขตสูงสุดของอัตราส่วนการประมาณค่าrที่พบได้ในทุกกรณีที่เป็นไปได้ของปัญหา ในทำนองเดียวกันอัตราส่วนประสิทธิภาพเชิงอะซิมโทติกคือ: $\mathrm {P} _{A}$ $R_{A}^{\infty }$

R_{A}^{\infty }=\inf\{r\geq 1\mid \exists n\in \mathbb {Z} ^{+},R_{A}(x)\leq r,\forall x,|x|\geq n\}.

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

การรับประกันประสิทธิภาพ
	r -ประมาณ^{[ 12 ]}^{[ 13 ]}	ρ -ประมาณ	ข้อผิดพลาดที่เกี่ยวข้อง^{[ 13 ]}	ข้อผิดพลาดที่เกี่ยวข้อง^{[ 12 ]}	ข้อผิดพลาดสัมพัทธ์ปกติ^{[ 12 ]}^{[ 13 ]}	ข้อผิดพลาดสัมบูรณ์^{[ 12 ]}^{[ 13 ]}
สูงสุด: $f(x)\geq$	$r^{-1}\คณิตศาสตร์ {OPT}$	$\rho \mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT}$	$(1-c)\mathrm {OPT} +c\mathrm {แย่ที่สุด}$	$\mathrm {OPT} -c$
นาที: $f(x)\leq$	$r\mathrm {OPT}$	$\rho \mathrm {OPT}$	$(1+c)\คณิตศาสตร์ {OPT}$	$(1-c)^{-1}\mathrm {OPT}$	$(1-c)^{-1}\mathrm {OPT} +c\mathrm {WORST}$	$\mathrm {OPT} +c$

เงื่อนไขเอปซิลอน

ในเอกสารทางวิชาการ อัตราส่วนการประมาณค่าสำหรับปัญหาการเพิ่มค่าสูงสุด (ลดค่าต่ำสุด) ของc - ϵ (min: c + ϵ) หมายความว่าอัลกอริทึมมีอัตราส่วนการประมาณค่าc ∓ ϵ สำหรับ ϵ > 0 ใดๆ แต่อัตราส่วนนี้ไม่ได้ (หรือไม่สามารถ) แสดงให้เห็นสำหรับ ϵ = 0 ตัวอย่างเช่น อัตราส่วนความไม่สามารถประมาณค่าที่เหมาะสมที่สุด — การไม่มีอยู่ของการประมาณค่า — ของ 7 / 8 + ϵ สำหรับอินสแตนซ์ MAX-3SAT ที่น่าพอใจ เนื่องจากJohan Håstad [ ^{14 ] ดัง}ที่กล่าวไว้ก่อนหน้านี้ เมื่อc = 1 ปัญหาจะกล่าวได้ว่ามี รูปแบบการประมาณค่าแบบพหุ นาม เวลา

เทอม ϵ อาจปรากฏขึ้นเมื่ออัลกอริทึมการประมาณค่าทำให้เกิดข้อผิดพลาดแบบคูณและข้อผิดพลาดคงที่ ในขณะที่ค่าที่เหมาะสมที่สุดของอินสแตนซ์ขนาดnมีค่าเข้าสู่อนันต์เมื่อnมีค่ามากขึ้น ในกรณีนี้ อัตราส่วนการประมาณค่าคือc ∓ k / OPT = c ∓ o(1) สำหรับค่าคงที่cและk บาง ค่า เมื่อกำหนด ϵ > 0 ใดๆ เราสามารถเลือกN ที่มีค่ามากพอ เพื่อให้เทอมk / OPT < ϵ สำหรับทุกn ≥ Nสำหรับทุก ϵ ที่กำหนดไว้ อินสแตนซ์ขนาดn < Nสามารถแก้ไขได้ด้วยวิธีการแบบ brute force ซึ่งแสดงให้เห็นถึงอัตราส่วนการประมาณค่า — การมีอยู่ของอัลกอริทึมการประมาณค่าที่มีการรับประกัน — ของc ∓ ϵ สำหรับทุก ϵ > 0

ดูเพิ่มเติม

การวิเคราะห์การครอบงำจะพิจารณาการรับประกันในแง่ของลำดับของคำตอบที่คำนวณได้
PTAS - ประเภทของอัลกอริธึมประมาณค่าที่ใช้ค่าอัตราส่วนการประมาณเป็นพารามิเตอร์
อัลกอริทึมการประมาณค่าแบบพารามิเตอร์ - อัลกอริทึมการประมาณค่าประเภทหนึ่งที่ทำงานในเวลาFPT
APXคือกลุ่มของปัญหาที่มีอัลกอริทึมการประมาณค่าแบบคงที่
การลดแบบรักษาค่าประมาณ
อัลกอริทึมที่แม่นยำ

การอ้างอิง

^ ^a ^b Bernard., Shmoys, David (2011). การออกแบบอัลกอริธึมการประมาณค่า . สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 9780521195270. OCLC 671709856 .{{cite book}}: CS1 maint: multiple names: authors list (link)
^ Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). "อัลกอริทึมการประมาณค่าสำหรับการจัดตารางเวลาเครื่องจักรคู่ขนานที่ไม่เกี่ยวข้องกัน" การเขียนโปรแกรมทางคณิตศาสตร์46 ( 1– 3): 259– 271. CiteSeerX 10.1.1.115.708 . doi : 10.1007/BF01585745 . ISSN 0025-5610 . S2CID 206799898 .
^ Agrawal, Ajit; Klein, Philip; Ravi, R. (1991). "When trees collide" . Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 . New Orleans, Louisiana, United States: ACM Press. pp. 134– 144. doi : 10.1145/103418.103437 . ISBN 978-0-89791-397-3S2CID 1245448
^ Goemans, Michel X.; Williamson, David P. (พฤศจิกายน 1995). "อัลกอริทึมการประมาณค่าที่ดีขึ้นสำหรับปัญหาการตัดสูงสุดและความพึงพอใจโดยใช้การเขียนโปรแกรมแบบกึ่งกำหนด" J. ACM . 42 (6): 1115– 1145. CiteSeerX 10.1.1.34.8500 . doi : 10.1145/227683.227684 . ISSN 0004-5411 . S2CID 15794408 .
^ Khot, Subhash; Regev, Oded (2008-05-01). "การครอบคลุมจุดยอดอาจยากที่จะประมาณค่าให้อยู่ภายใน 2−ε"วารสารวิทยาการคอมพิวเตอร์และระบบ ความซับซ้อนในการคำนวณ 2003. 74 (3): 335– 349. doi : 10.1016/j.jcss.2007.06.019 .
^ Karpinski, Marek; Lampis, Michael; Schmied, Richard (2015-12-01). "ขอบเขตความไม่สามารถประมาณค่าใหม่สำหรับ TSP". Journal of Computer and System Sciences . 81 (8): 1665– 1677. arXiv : 1303.6437 . doi : 10.1016/j.jcss.2015.06.003 .
↑ไฟกี, อูรีเอล; โกลด์วาสเซอร์, ชาฟี; โลวาสซ์, ลาสซโล; ซาฟรา, ชมูเอล; เซเกดี, มาริโอ (มีนาคม 1996) "การพิสูจน์เชิงโต้ตอบและความแข็งของกลุ่มใกล้เคียง " เจ . พล.อ. 43 (2): 268– 292. ดอย : 10.1145/226643.226652 . ISSN 0004-5411 .
^ Arora, Sanjeev; Safra, Shmuel (มกราคม 1998). "การตรวจสอบความน่าจะเป็นของหลักฐาน: ลักษณะเฉพาะใหม่ของ NP" . J. ACM . 45 (1): 70– 122. doi : 10.1145/273865.273901 . ISSN 0004-5411 . S2CID 751563 .
^ Johnson, David S. (1974-12-01). "อัลกอริทึมการประมาณค่าสำหรับปัญหาเชิงการจัดเรียง" . วารสารวิทยาการคอมพิวเตอร์และระบบ . 9 (3): 256– 278. doi : 10.1016/S0022-0000(74)80044-9 .
^ Arora, S. (ตุลาคม 1996). "แผนการประมาณค่าแบบใช้เวลาพหุนามสำหรับปัญหา TSP แบบยุคลิดและปัญหาทางเรขาคณิตอื่นๆ". รายงานการประชุมวิชาการครั้งที่ 37 ว่าด้วยพื้นฐานของวิทยาศาสตร์คอมพิวเตอร์หน้า 2–11 . CiteSeerX 10.1.1.32.3376 . doi : 10.1109/SFCS.1996.548458 . ISBN 978-0-8186-7594-2. S2CID 1499391 .
^ Arora, S. (ตุลาคม 1997). "วิธีการประมาณค่าแบบเกือบเชิงเส้นสำหรับปัญหา TSP แบบยุคลิดและปัญหาทางเรขาคณิตอื่นๆ". รายงานการประชุมสัมมนาประจำปีครั้งที่ 38 ว่าด้วยพื้นฐานของวิทยาการคอมพิวเตอร์หน้า 554–563 . doi : 10.1109/SFCS.1997.646145 . ISBN 978-0-8186-8197-4. S2CID 10656723 .
^ ^a ^b ^c ^d ^e G. Ausiello; P. Crescenzi; G. Gambosi; V. Kann; A. Marchetti-Spaccamela; M. Protasi (1999). ความซับซ้อนและการประมาณค่า: ปัญหาการหาค่าเหมาะสมเชิงการจัดเรียงและคุณสมบัติการประมาณค่า
^ ^a ^b ^c ^d ^e Viggo Kann (1992). ว่าด้วยความสามารถในการประมาณค่าของปัญหาการหาค่าเหมาะสมที่สุดแบบ NP-complete (PDF )
^ Johan Håstad (1999). "ผลลัพธ์ความไม่สามารถประมาณค่าที่เหมาะสมบางประการ" . วารสาร ACM . 48 (4): 798– 859. CiteSeerX 10.1.1.638.2808 . doi : 10.1145/502090.502098 . S2CID 5120748 .

ลิงก์ภายนอก

Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek KarpinskiและGerhard Woeginger บทสรุปของปัญหาการปรับให้เหมาะสมของNP

[Bernard._2011-1] Bernard., Shmoys, David (2011). การออกแบบอัลกอริธึมการประมาณค่า . สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์. ISBN 9780521195270. OCLC 671709856 .{{cite book}}: CS1 maint: multiple names: authors list (link)

[2] Lenstra, Jan Karel; Shmoys, David B.; Tardos, Éva (1990-01-01). "อัลกอริทึมการประมาณค่าสำหรับการจัดตารางเวลาเครื่องจักรคู่ขนานที่ไม่เกี่ยวข้องกัน" การเขียนโปรแกรมทางคณิตศาสตร์46 ( 1– 3): 259– 271. CiteSeerX 10.1.1.115.708 . doi : 10.1007/BF01585745 . ISSN 0025-5610 . S2CID 206799898 .

[3] Agrawal, Ajit; Klein, Philip; Ravi, R. (1991). "When trees collide" . Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 . New Orleans, Louisiana, United States: ACM Press. pp. 134– 144. doi : 10.1145/103418.103437 . ISBN 978-0-89791-397-3S2CID 1245448

[4] Goemans, Michel X.; Williamson, David P. (พฤศจิกายน 1995). "อัลกอริทึมการประมาณค่าที่ดีขึ้นสำหรับปัญหาการตัดสูงสุดและความพึงพอใจโดยใช้การเขียนโปรแกรมแบบกึ่งกำหนด" J. ACM . 42 (6): 1115– 1145. CiteSeerX 10.1.1.34.8500 . doi : 10.1145/227683.227684 . ISSN 0004-5411 . S2CID 15794408 .

[5] Khot, Subhash; Regev, Oded (2008-05-01). "การครอบคลุมจุดยอดอาจยากที่จะประมาณค่าให้อยู่ภายใน 2−ε"วารสารวิทยาการคอมพิวเตอร์และระบบ ความซับซ้อนในการคำนวณ 2003. 74 (3): 335– 349. doi : 10.1016/j.jcss.2007.06.019 .

[6] Karpinski, Marek; Lampis, Michael; Schmied, Richard (2015-12-01). "ขอบเขตความไม่สามารถประมาณค่าใหม่สำหรับ TSP". Journal of Computer and System Sciences . 81 (8): 1665– 1677. arXiv : 1303.6437 . doi : 10.1016/j.jcss.2015.06.003 .

[7] ไฟกี, อูรีเอล; โกลด์วาสเซอร์, ชาฟี; โลวาสซ์, ลาสซโล; ซาฟรา, ชมูเอล; เซเกดี, มาริโอ (มีนาคม 1996) "การพิสูจน์เชิงโต้ตอบและความแข็งของกลุ่มใกล้เคียง " เจ . พล.อ. 43 (2): 268– 292. ดอย : 10.1145/226643.226652 . ISSN 0004-5411 .

[8] Arora, Sanjeev; Safra, Shmuel (มกราคม 1998). "การตรวจสอบความน่าจะเป็นของหลักฐาน: ลักษณะเฉพาะใหม่ของ NP" . J. ACM . 45 (1): 70– 122. doi : 10.1145/273865.273901 . ISSN 0004-5411 . S2CID 751563 .

[9] Johnson, David S. (1974-12-01). "อัลกอริทึมการประมาณค่าสำหรับปัญหาเชิงการจัดเรียง" . วารสารวิทยาการคอมพิวเตอร์และระบบ . 9 (3): 256– 278. doi : 10.1016/S0022-0000(74)80044-9 .

[10] Arora, S. (ตุลาคม 1996). "แผนการประมาณค่าแบบใช้เวลาพหุนามสำหรับปัญหา TSP แบบยุคลิดและปัญหาทางเรขาคณิตอื่นๆ". รายงานการประชุมวิชาการครั้งที่ 37 ว่าด้วยพื้นฐานของวิทยาศาสตร์คอมพิวเตอร์หน้า 2–11 . CiteSeerX 10.1.1.32.3376 . doi : 10.1109/SFCS.1996.548458 . ISBN 978-0-8186-7594-2. S2CID 1499391 .

[11] Arora, S. (ตุลาคม 1997). "วิธีการประมาณค่าแบบเกือบเชิงเส้นสำหรับปัญหา TSP แบบยุคลิดและปัญหาทางเรขาคณิตอื่นๆ". รายงานการประชุมสัมมนาประจำปีครั้งที่ 38 ว่าด้วยพื้นฐานของวิทยาการคอมพิวเตอร์หน้า 554–563 . doi : 10.1109/SFCS.1997.646145 . ISBN 978-0-8186-8197-4. S2CID 10656723 .

[ausiello99complexity-12] G. Ausiello; P. Crescenzi; G. Gambosi; V. Kann; A. Marchetti-Spaccamela; M. Protasi (1999). ความซับซ้อนและการประมาณค่า: ปัญหาการหาค่าเหมาะสมเชิงการจัดเรียงและคุณสมบัติการประมาณค่า

[kann92onthe-13] Viggo Kann (1992). ว่าด้วยความสามารถในการประมาณค่าของปัญหาการหาค่าเหมาะสมที่สุดแบบ NP-complete (PDF )

[hastad99someoptimal-14] Johan Håstad (1999). "ผลลัพธ์ความไม่สามารถประมาณค่าที่เหมาะสมบางประการ" . วารสาร ACM . 48 (4): 798– 859. CiteSeerX 10.1.1.638.2808 . doi : 10.1145/502090.502098 . S2CID 5120748 .

[

[

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[

[

[

[

14 ] ดัง