The Gas Station Problem

Suppose you want to go on a road trip across the Unites States. Your plan is to go from New York City to San Francisco. With sky rocketing gas prices, how would you plan your trip to spend as little money as possible? Information about gas prices in a given area is available from sites such as AAA.com or GasPriceWatch.com. How can you use this information to plan the cheapest route? In this talk I will describe algorithms for this problem, as well as other problems in this framework.