A NOTE ON THE PRIZE COLLECTING TRAVELING SALESMAN PROBLEM

被引：180

作者：

BIENSTOCK, D

GOEMANS, MX

SIMCHILEVI, D

WILLIAMSON, D

机构：

[1] MIT,DEPT MATH,CAMBRIDGE,MA 02139

[2] MIT,DEPT COMP SCI,CAMBRIDGE,MA 02139

来源：

MATHEMATICAL PROGRAMMING | 1993年 / 59卷 / 03期

关键词：

LINEAR PROGRAMMING; PRIZE COLLECTING; ROUNDING FRACTIONAL SOLUTIONS; TRAVELING SALESMAN PROBLEM; WORST-CASE ANALYSIS;

D O I：

10.1007/BF01581256

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. We present an approximation algorithm with constant bound. The algorithm is based on Christofides' algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.

引用

页码：413 / 420

页数：8

共 10 条

[1] THE PRIZE COLLECTING TRAVELING SALESMAN PROBLEM [J].

BALAS, E .

NETWORKS, 1989, 19 (06) :621-636

[2]

Christofides N., 1976, 388 CARN MELL U GRAD

[3]

GOEMANS MX, 1990, 1ST P ACM SIAM S DIS

[4] TRAVELING-SALESMAN PROBLEM AND MINIMUM SPANNING TREES [J].

HELD, M ;

KARP, RM .

OPERATIONS RESEARCH, 1970, 18 (06) :1138-&

[5]

Johnson D.S., 1985, TRAVELING SALESMAN P, P145

[6]

Lenstra J. K., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P217, DOI 10.1109/SFCS.1987.8

[7] SOME CONNECTIVITY PROPERTIES OF EULERIAN GRAPHS [J].

LOVASZ, L .

ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1976, 28 (1-2) :129-138

[8]

Lovasz L., 1979, COMBINATORIAL PROBLE

[9]

SHMOYS D, 1988, IN PRESS INFORMATION

[10]

WOLSEY LA, 1980, MATH PROGRAM STUD, V13, P121, DOI 10.1007/BFb0120913

← 1 →