Two short notes on the on-line travelling salesman: handling times and lookahead

作     者：Damaschke, P 

作者机构：Chalmers Univ Technol Dept Comp Sci S-41296 Gothenburg Sweden 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2002年第289卷第1期

页      面：845-852页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：on-line algorithms travelling salesman handling times lookahead 

摘      要：We study extensions of the on-line travelling salesman problem. Our results are: The optimal competitive ratio 2 for arbitrary metric spaces also holds in the case of nonzero handling times. The optimal competitive ratio 3/2 on the half-line cannot be improved by randomization, but there is a 4/3-competitive algorithm under the assumption that the server is notified when the last request has been released. This ratio is also optimal. (C) 2002 Elsevier Science B.V. All rights reserved.