Loading...
Please wait, while we are loading the content...
Similar Documents
Implementing the traveling repairman problem on open street maps
| Content Provider | Indraprastha Institute of Information Technology, Delhi |
|---|---|
| Author | Gogia, Jagrati Jain, Siddhant |
| Abstract | We wish to study and implement the Traveling Repairman Problem (TRP) on Open Street Maps data. The fact that OSM is a freely editable map of the world is a major motivation behind using it. We observe that TRP which seems to be a simple variant of the extensively studied Traveling Salesman Problem (TSP), actually turns out to be much di erent in character. We focus on the 8-approximation algorithm given by Sudan et. al. for solving the TRP. All known TRP algorithms solve k-TSP or k-MST as a sub-routine. We have mainly focused on a 5-approximation algorithm for k-MST by Garg which uses a Lagrangean relaxation technique employing a primal-dual approximation algorithm for the prize-collecting Steiner tree (PCST) problem. Further, we have used the local ratio technique for implementing the primal-dual method of approximation for solving the PCST problem. |
| File Format | |
| Language | English |
| Access Restriction | Authorized |
| Subject Keyword | Traveling repairman problem Traveling salesman problem K-MST Lagrangean relaxation Primal-dual approximation Local ratio |
| Content Type | Text |
| Educational Degree | Bachelor of Technology (B.Tech.) |
| Subject | Data processing & computer science |
