The online Prize-Collecting Traveling Salesman Problem

被引：35

作者：

Ausiello, Giorgio ^{[1
]}

Bonifaci, Vincenzo ^{[1
,2
]}

Laura, Luigi ^{[1
]}

机构：

[1] Univ Roma La Sapienza, Dipartimento Informat & Sistemist, I-00185 Rome, Italy

[2] Univ Aquila, Dipartimento Ingn Elettr, I-67040 Laquila, Italy

来源：

INFORMATION PROCESSING LETTERS | 2008年 / 107卷 / 06期

关键词：

on-line algorithms; analysis of algorithms; combinatorial problems;

D O I：

10.1016/j.ipl.2008.03.002

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study the online version of the Prize-Collecting Traveling Salesman Problem (PCTSP), a generalization of the Traveling Salesman Problem (TSP). In the TSP, the salesman has to visit a set of cities while minimizing the length of the overall tour. In the PCTSP, each city has a given weight and penalty, and the goal is to collect a given quota of the weights of the cities while minimizing the length of the tour plus the penalties of the cities not in the tour. In the online version, cities are disclosed over time. We give a 7/3-competitive algorithm for the problem, which compares with a lower bound of 2 on the competitive ratio of any deterministic algorithm. We also show how our approach can be combined with an approximation algorithm in order to obtain an O(1)-competitive algorithm that runs in polynomial time. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：199 / 204

页数：6

共 12 条

[1]

Ascheuer N, 2000, LECT NOTES COMPUT SC, V1770, P639

[2] Algorithms for the on-line Quota Traveling Salesman Problem [J].

Ausiello, G ;

Demange, M ;

Laura, L ;

Paschos, V .

INFORMATION PROCESSING LETTERS, 2004, 92 (02) :89-94

[3] Algorithms for the on-line travelling salesman [J].

Ausiello, G ;

Feuerstein, E ;

Leonardi, S ;

Stougie, L ;

Talamo, M .

ALGORITHMICA, 2001, 29 (04) :560-581

[4]

Ausiello G, 2000, LECT NOTES COMPUT SC, V1767, P1

[5]

AUSIELLO G, 2006, 0806 TR U ROM SAP DE

[6] New approximation guarantees for minimum-weight k-trees and prize-collecting salesmen [J].

Awerbuch, B ;

Azar, Y ;

Blum, A ;

Vempala, S .

SIAM JOURNAL ON COMPUTING, 1998, 28 (01) :254-262

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

BALAS, E .

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

[8]

Blum A., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P442, DOI 10.1145/237814.237992

[9]

CHEUNG SY, 1994, P IEEE INFOCOM 94 C, V2, P840

[10]

Dell'Amico M., 1995, International Transactions in Operational Research, V2, P297, DOI 10.1111/j.1475-3995.1995.tb00023.x

← 1 2 →