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

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.