| ชื่อเรื่อง | : | An improved approximation algorithm for the s-t path movement problem |
| นักวิจัย | : | Jindaluang W. , Chawachat J. , Chouvatut V. , Fakcharoenphol J. , Kantabutra S. |
| คำค้น | : | - |
| หน่วยงาน | : | มหาวิทยาลัยเชียงใหม่ |
| ผู้ร่วมงาน | : | - |
| ปีพิมพ์ | : | 2560 |
| อ้างอิง | : | 01252526 , 2-s2.0-85010824713 , https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85010824713&origin=inward , http://cmuir.cmu.ac.th/jspui/handle/6653943832/40989 |
| ที่มา | : | - |
| ความเชี่ยวชาญ | : | - |
| ความสัมพันธ์ | : | - |
| ขอบเขตของเนื้อหา | : | - |
| บทคัดย่อ/คำอธิบาย | : | © 2017, Chiang Mai University. All rights reserved. This paper considers a movement problem that minimizes the maximum movement of pebbles on a graph to form a path from source vertex s to destination vertex t. The best known algorithm for this problem is a 7-approximation algorithm developed by Berman, Demaine, and Zadimoghaddam in 2011. We refine the analysis of Berman et. al. to obtain an (3 + ϵ)-approximation algorithm for any constant ϵ > 0. This problem is a subroutine used by Berman et. al. for finding a solution to the connectivity movement problem. Using our improved algorithm as a subroutine, the approximation ratio for the connectivity movement problem improves from 136 to 104 + ϵ. |
| บรรณานุกรม | : |
Jindaluang W. , Chawachat J. , Chouvatut V. , Fakcharoenphol J. , Kantabutra S. . (2560). An improved approximation algorithm for the s-t path movement problem.
เชียงใหม่ : มหาวิทยาลัยเชียงใหม่ . Jindaluang W. , Chawachat J. , Chouvatut V. , Fakcharoenphol J. , Kantabutra S. . 2560. "An improved approximation algorithm for the s-t path movement problem".
เชียงใหม่ : มหาวิทยาลัยเชียงใหม่ . Jindaluang W. , Chawachat J. , Chouvatut V. , Fakcharoenphol J. , Kantabutra S. . "An improved approximation algorithm for the s-t path movement problem."
เชียงใหม่ : มหาวิทยาลัยเชียงใหม่ , 2560. Print. Jindaluang W. , Chawachat J. , Chouvatut V. , Fakcharoenphol J. , Kantabutra S. . An improved approximation algorithm for the s-t path movement problem. เชียงใหม่ : มหาวิทยาลัยเชียงใหม่ ; 2560.
|
ridm@nrct.go.th ระบบคลังข้อมูลงานวิจัยไทย รายการโปรดที่คุณเลือกไว้
