อัลกอริทึมแบบประมาณสำหรับปัญหาการตัดมากสุดในแบบจำลองสุ่มของกราฟหนาแน่น

Approximation algorithms for MAX-CUT on a random model of dense graphs

Name: ภานุ วจะโนภาส

ThaSH: มหาวิทยาลัยเกษตรศาสตร์ -- วิทยานิพนธ์. วศ.ม. (วิศวกรรมคอมพิวเตอร์) 2564

Classification :.LCCS: QA76.9.A43

ThaSH: มหาวิทยาลัยเกษตรศาสตร์. สาขาวิศวกรรมคอมพิวเตอร์ -- วิทยานิพนธ์

ThaSH: ขั้นตอนวิธีการประมาณ

ThaSH: ฮิวริสติกอัลกอริทึม

ThaSH: การโปรแกรมเชิงเส้น

Abstract: ปัญหาการตัดมากที่สุดต้องการหาการแบ่งโหนดของกราฟออกเป็นสองส่วน ให้มีจำนวนเส้นเชื่อมที่ข้ามระหว่างทั้งสองส่วนมากที่สุด ในกรณีของกราฟหนาแน่น หรือกราฟที่ถูกสุ่มด้วยเงื่อนไขบางประการ เป็นที่ทราบกันว่ามีแบบแผนการประมาณในเวลาพหุนามสำหรับปัญหานี้ ซึ่งหมายความว่ามีอัลกอริทึมที่ทำงานในเวลาพหุนาม ซึ่งสามารถประมาณให้เข้าใกล้คำตอบที่ดีที่สุดตามที่ต้องการ โดยแลกกับเวลาการทำงานที่นานขึ้น วิทยานิพนธ์ชิ้นนี้นำเสนอปัญหาดังกล่าวกับแบบจำลองสุ่มที่เกี่ยวข้องกับทั้งสองกรณีที่ได้กล่าวไป โดยเงื่อนไขของแบบจำลอง ได้แก่ แต่ละเส้นเชื่อมของกราฟที่สนใจถูกสุ่มให้คงไว้จากอีกกราฟหนาแน่นที่ไม่อาจทราบได้อย่างอิสระ ด้วยความน่าจะเป็นผกผันกับรากที่สองของลอการิทึมของจำนวนโหนดและส่งผลให้กราฟที่ได้ไม่ใช่กราฟหนานแน่นด้วยความน่าจะเป็นสูง นอกจากนั้นงานชิ้นนี้แสดงให้เห็นว่า อัลกอริทึมของ de la Vega สามารถถูกนำมาดัดแปลงให้ยังคงเป็นแบบแผนการประมาณในเวลาพหุนามสำหรับแบบจำลองนี้ The maximum cut problem finds a partition of a graph that maximizes the number of crossing edges. When the graph is dense or sampled based on certain planted assumptions, polynomial-time approximation schemes exist. In other words, there exists a polynomial-time algorithm that can closely approximate the optimal solution by trading off between precision and running time. This thesis presents another random model relating to both cases. The conditions are that a graph has its edges sampled from an unknown dense graph independently with probability inverse to the square root of the logarithm of the number of vertices; this input graph is hence no longer dense. Furthermore, it is shown that de la Vega's algorithm can be modified to work as the polynomial-time approximation scheme for this model.

มหาวิทยาลัยเกษตรศาสตร์. สำนักหอสมุด

Address: กรุงเทพมหานคร

Email: tdckulib@ku.ac.th

Name: จิตร์ทัศน์ ฝักเจริญผล

Role: อาจารย์ที่ปรึกษาวิทยานิพนธ์หลัก

Name: ธนาวินท์ รักธรรมานนท์

Role: อาจารย์ที่ปรึกษาวิทยานิพนธ์ร่วม

Created: 2564

Modified: 2568-07-22

Issued: 2568-07-22

วิทยานิพนธ์/Thesis

application/pdf

URL: https://www.lib.ku.ac.th/KUthesis/2564/phanu-vaj-all.pdf

CallNumber: QA76.9.A43 .ภ25

tha

DegreeName: วิศวกรรมศาสตรมหาบัณฑิต

Level: ปริญญาโท

Descipline: วิศวกรรมคอมพิวเตอร์

Grantor: มหาวิทยาลัยเกษตรศาสตร์

©copyrights มหาวิทยาลัยเกษตรศาสตร์

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	phanu-vaj-all.pdf	4.15 MB

ใช้เวลา

0.036876 วินาที