Paper Info
Title
The Canadian Tour Operator Problem on paths: tight bounds and resource augmentation
Abstract
In the prize-collecting travelling salesman problem, we are given a weighted graph $$G=(V,E)$$G=(V,E) with edge weights $$\\ell :E\\rightarrow \\mathbb {R}_+$$ℓ:EźR+, a special vertex $$r\\in V$$rźV, penalties $$\\pi :V\\rightarrow \\mathbb {R}_+$$ź:VźR+ and the goal is to find a closed tour $$T$$T such that $$r\\in V(T)$$rźV(T) and such that the cost $$\\ell (T)+\\pi (V\\setminus V(T))$$ℓ(T)+ź(V\\V(T)), which is the sum of the edges in the tour and the cost of the vertices not spanned by $$T$$T, is minimized. We consider an online variant of the prize-collecting travelling salesman problem related to graph exploration. In the Canadian Tour Operator Problem the task is to find a closed route for a tourist bus in a given network $$G=(V,E)$$G=(V,E) in which some edges are blocked by avalanches. An online algorithm learns from a blocked edge only when reaching one of its endpoints. The bus operator has the option to avoid visiting each node $$v\\in V$$vźV by paying a refund of $$\\pi (v)$$ź(v) to the tourists. The goal consists of minimizing the sum of the travel costs and the refunds. We study the problem on a simple (weighted) path and prove tight bounds on the competitiveness of deterministic algorithms. Specifically, we give an algorithm with competitive ratio equal to the golden ratio $$\\phi =(1+\\sqrt{5})/2$$ź=(1+5)/2. We also study the effect of resource augmentation, where the online algorithm either pays a discounted cost for traversing edges or for the penalties.
Year
DOI
Venue
2016
10.1007/s10878-015-9905-7
J. Comb. Optim.
Keywords
Field
DocType
Online computation,Competitive analysis,Resource augmentation,Graph exploration
Graph,Online algorithm,Mathematical optimization,Combinatorics,Operator problem,Vertex (geometry),Golden ratio,Travelling salesman problem,Operator (computer programming),Mathematics,Competitive analysis
Journal
Volume
Issue
ISSN
32
3
1382-6905
Citations 
PageRank 
References 
0
0.34
9
Authors
2
Name
Order
Citations
PageRank
sabine buttner150.78
Sven O. Krumke230836.62