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.


- No comments Not publicly viewable

Add a comment

You are not allowed to comment on this entry as it has restricted commenting permissions.

PhD Comics

January 2007

Mo Tu We Th Fr Sa Su
Dec |  Today  | Feb
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31            

Search this blog


Most recent comments

  • Can't beat a German Market. by on this entry
  • Imagine Shiva in Words by this stotra (Thanks to Ravana) by Yogendra on this entry
  • This is the favorite and most inspiring stothram for me. It invokes the manliness in ourself to rise… by Bhargav on this entry
  • Went last night and it was really good. First time i have been and will definatly return next year. by Mad Dozza on this entry
  • strota really purifies soul by shailendra on this entry

Blog archive

Not signed in
Sign in

Powered by BlogBuilder