The Canadian Tour Operator Problem (Online Graph Exploration with Disposal)
Sabine Büttner · 2012
node v ∈ V by paying a refund of p(v) to the tourists. The goal is to minimize the sum of the travel costs and the refunds. We show that no deterministic or randomized algorithm can achieve a bounded competitive ratio for the CTOP on general graphs. Further, we present a φ-competitive algorithm for the line and give a Ski-Rental like 3-competitive algorithm for tree networks. Joint work with Sven O. Krumke.