#
All entries for Monday 29 January 2007

## January 29, 2007

### Tourist Agency Problem

A tourist agency anonuces an interesting scheme for all tourist who are interested in having a tour of as many cities as possible in europe. Given an initial budget B , tourist agency works as follows.

Given the map of the cities and the prices between the cities are given as a weighted directed graph G = {V, E, p}. There are different cities V = {C_1, C_2, ..., C_n} and from every city there are some flight connections to some other cities (C_i, C_j) \in E and the price of the flights between cities is fixed in advance p(C_i, C_j). Starting from a city C_i and a budget B, tourist agency picks an amount d < B, such that there exists a city C_j such that p(C_i, C_j) = d. If the tourist agency can not choose such a number d and the remaining budget B is greater than 0, then toursit agency agrees to pay a high price as penalty to the tourists and thus toursit agency loses. Otherwise the tourists pick a city such that flight price to the destination city is d unit and take the flight. Tourist agency then updates the budget B to B-d and the tour continues. The aim of the tourist agency is to reach a city with 0 budget.

Given a map and an initial budget, find optimal strategy for the tourist guide and the tourists.