The Canadian Tour Operator Problem on paths: tight bounds and resource augmentation

Sabine Büttner () and Sven O. Krumke ()
Additional contact information
Sabine Büttner: University of Kaiserslautern
Sven O. Krumke: University of Kaiserslautern

Journal of Combinatorial Optimization, 2016, vol. 32, issue 3, No 12, 842-854

Abstract: 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.

Keywords: Online computation; Competitive analysis; Resource augmentation; Graph exploration (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9905-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:32:y:2016:i:3:d:10.1007_s10878-015-9905-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9905-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().