การปรับปรุงขั้นตอนวิธีแบบประมาณสำหรับปัญหาการติดตามวิถี

An improved approximation algorithm for tracking paths

Name: คุณานนต์ บุรเทพ

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

Classification :.LCCS: QA76.9.A43

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

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

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

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

Abstract: วิทยานิพนธ์ฉบับนี้จัดทำขึ้นเพื่อนำเสนอขั้นตอนวิธีสำหรับปัญหาสองปัญหา ปัญหาแรกคือปัญหา Vertex Multicut บนต้นไม้ที่ต้องการหาเซตของจุดยอดที่มีค่าถ่วงน้ำหนักน้อยที่สุดที่เมื่อตัดออกแล้วทำให้ทุกคู่จุดยอดที่ได้ถูกกำหนดมาให้ไม่มีวิถีถึงกัน วิทยานิพนธ์นี้ได้นำเสนอขั้นตอนวิธีแบบประมาณที่อัตราส่วนการประมาณเท่ากับ 2 ปัญหาที่สองได้แก่ปัญหา Tracking Paths ที่ต้องการหาเซตของจุดยอด T ที่ทำให้สามารถจำแนกวิถีทุกวิถีจากจุดเริ่มต้น s ไปจุดปลายทาง t ได้จากลำดับการจัดเรียงจุดยอดของวิถีในเซต T สำหรับปัญหาดังกล่าว งานวิจัยล่าสุดในปัจจุบันซึ่งเสนอโดย Václav Blažej, Pratibha Choudhary, Dušan Knop, Jan Matyáš Křišťan, Ondrej Suchy and Tomáš Valla [WAOA'21] เป็นขั้นตอนวิธีแบบประมาณที่อัตราส่วนการประมาณเท่ากับ 66 โดยใช้ขั้นตอนวิธีแบบประมาณสำหรับปัญหา Vertex Multicut บนต้นไม้ เมื่อนำขั้นตอนวิธีแบบประมาณสำหรับปัญหา Vertex Multicut ที่เราได้เสนอขึ้นทำให้สามารถลดค่าอัตราส่วนการประมาณจาก 66 เป็น 6 ได้สำหรับปัญหาดังกล่าว This thesis considers two related path problems in graphs. The first problem is the Vertex Multicut on Trees whose goal is to find the cheapest set of vertices that cut every given pair of vertices. We present a 2-approximation algorithm for this problem. Another problem is the Tracking Paths whose goal is to find the cheapest set of vertices such that every distinct path from source s to target t can be uniquely identified by an intersection pattern with those set of vertices. The 2-approximation algorithm for the Vertex Multicut on Trees can be used as a subroutine in the recent approximation algorithm presented by Václav Blažej, Pratibha Choudhary, Dušan Knop, Jan Matyáš Křišťan, Ondrej Suchy and Tomáš Valla [WAOA'21], improving approximation ratio from 66 to 6 for the Tracking Paths problem.

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

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/kunanon-bur-all.pdf

CallNumber: QA76.9.A43 .ค44

tha

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

Level: ปริญญาโท

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

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

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

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

ใช้เวลา

-0.977184 วินาที