หลักสูตร/ปี พ.ศ. วิศวกรรมศาสตรมหาบัณฑิต สาขาวิชาวิศวกรรมคอมพิวเตอร์ ปี พ.ศ. 2565
ภาคและปีการศึกษาที่สำเร็จการศึกษา ภาคฤดูร้อน ปีการศึกษา 2564
ประเภทโครงงาน
วิทยานิพนธ์
ชื่อโครงงานภาษาไทย
อัลกอริทึมแบบประมาณสำหรับปัญหาการตัดมากสุดในแบบจำลองสุ่มของกราฟหนาแน่น
ชื่อโครงงานภาษาอังกฤษ
Approximation Algorithms for MAX-CUT on a Random Model of Dense Graphs
ผู้พัฒนา
6314500265 ภานุ วจะโนภาส
อาจารย์ที่ปรึกษาหลัก
จิตร์ทัศน์ ฝักเจริญผล
อาจารย์ที่ปรึกษาร่วม
ธนาวินท์ รักธรรมานนท์
บทคัดย่อ
ปัญหาการตัดมากที่สุดต้องการหาการแบ่งโหนดของกราฟออกเป็นสองส่วน ให้มีจำนวนเส้นเชื่อมที่ข้ามระหว่างทั้งสองส่วนมากที่สุด ในกรณีของกราฟหนาแน่น หรือกราฟที่ถูกสุ่มด้วยเงื่อนไขบางประการ เป็นที่ทราบกันว่ามีแบบประมาณในเวลาพหุนามสำหรับปัญหานี้ ซึ่งหมายความว่า มีอัลกอริทึมที่ทำงานในเวลาพหุนาม ซึ่งสามารถประมาณให้เข้าใกล้คำตอบที่ดีที่สุดตามที่ต้องการ โดยแลกกับเวลาการทำงานที่นานขึ้น วิทยานิพนธ์ชิ้นนี้นำเสนอปัญหาดังกล่าวกับแบบจำลองสุ่มที่เกี่ยวข้องกับทั้งสองกรณีที่ได้กล่าวไป โดยเงื่อนไขของแบบจำลอง ได้แก่ แต่ละเส้นเชื่อมของกราฟที่สนใจถูกสุ่มให้คงไว้จากอีกกราฟหนาแน่นที่ไม่อาจทราบได้อย่างอิสระ ด้วยความน่าจะเป็นผกผันกับรากที่สองของลอการิทึมของจำนวนโหนด และส่งผลให้กราฟที่ได้ไม่ใช่กราฟหนาแน่นด้วยความน่าจะเป็นสูง นอกจากนั้นงานชิ้นนี้แสดงให้เห็นว่า อัลกอริทึมของ de la Vega สามารถถูกนำมาดัดแปลงให้ยังคงเป็นแบบแผนการประมาณในเวลาพหุนามสำหรับแบบจำลองนี้
Abstract
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.
คำสำคัญ (Keywords)
-
เว็บไซต์โครงงาน
-
วีดีโอคลิปของโครงงาน
-
ที่เก็บเวอร์ชันซอร์สโค้ด
-
ผู้นำเข้าข้อมูลครั้งแรก
ภานุ
วจะโนภาส
(g6314500265)
แก้ไขครั้งสุดท้าย
เมื่อ Sept. 1, 2022, 3:32 p.m. โดย
ภานุ
วจะโนภาส
(g6314500265)
สถานะการอนุมัติ
รออนุมัติ