Better approximations for max TSP

被引:33
作者
Hassin, R [1 ]
Rubinstein, S
机构
[1] Tel Aviv Univ, Sch Math Sci, Dept Stat & Operat Res, IL-69978 Tel Aviv, Israel
[2] Carnegie Mellon Univ, GSIA, Pittsburgh, PA 15213 USA
关键词
analysis of algorithms; maximum traveling salesman; maximum latency TSP;
D O I
10.1016/S0020-0190(00)00097-1
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We combine two known polynomial time approximation algorithms for the maximum traveling salesman problem to obtain a randomized algorithm which outputs a solution with expected value of at least r. times the optimal one for any given r < 25/33. (C) 2000 Elsevier Science B.V. All rights reserved.
引用
收藏
页码:181 / 186
页数:6
相关论文
共 5 条
  • [1] Barvinok A, 1998, LECT NOTES COMPUT SC, V1412, P195
  • [2] Approximating capacitated routing and delivery problems
    Chalasani, P
    Motwani, R
    [J]. SIAM JOURNAL ON COMPUTING, 1999, 28 (06) : 2133 - 2149
  • [3] An approximation algorithm for the maximum traveling salesman problem
    Hassin, R
    Rubinstein, S
    [J]. INFORMATION PROCESSING LETTERS, 1998, 67 (03) : 125 - 130
  • [4] KOSTOCHKA AV, 1985, UPRAVLYAEMYE SISTEMY, V26, P55
  • [5] SERDYUKOV AI, 1984, UPRAVLYAEMYE SISTEMY, V25, P80