3-Approximation algorithm for a two depot, heterogeneous traveling salesman problem

被引：19
作者：
Yadlapalli, Sai [1 ]
Rathinam, Sivakumar [1 ]
Darbha, Swaroop [1 ]
机构：
[1] Texas A&M Univ, College Stn, TX 77843 USA
来源：
OPTIMIZATION LETTERS | 2012年 / 6卷 / 01期
基金：
美国国家科学基金会;
关键词：
Traveling salesman problem; Heterogeneous vehicle; Approximation algorithm; MULTIPLE DEPOT;
D O I：
10.1007/s11590-010-0256-0
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We present the first approximation algorithm for a two depot, heterogeneous traveling salesman problem with an approximation ratio of 3 when the costs are symmetric and satisfy the triangle inequality.
引用
收藏
页码：141 / 152
页数：12
相关论文
共 23 条
[1]  
[Anonymous], 1994, Lecture notes in computer science
[2]  
[Anonymous], 1976, COMBINATORIAL OPTIMI
[3]  
[Anonymous], 2001, Approximation algorithms
[4]  
[Anonymous], 2005, Robotics: Science and Systems
[5]  
[Anonymous], 2009, ENCY OPTIMIZATION
[6]  
[Anonymous], HDB COMBINATORIAL OP
[7]  
[Anonymous], 1976, WORST CASE ANAL NEW
[8]  
Chandler PR, 2002, P AMER CONTR CONF, V1-6, P1831, DOI 10.1109/ACC.2002.1023833
[9]  
Chandler PR, 1998, P AMER CONTR CONF, P394, DOI 10.1109/ACC.1998.694698
[10]  
Ford LR, 1962, FLOWS NETWORKS
123