Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

To Fill or Not to Fill: The Gas Station Problem
(Extended Abstract)

Samir KhullerContact Information, Azarakhsh MalekianContact Information and Julián MestreContact Information

(1)  Department of Computer Science., University of Maryland, College Park, MD 20742, USA
Abstract
In this paper we study several routing problems that generalize shortest paths and the Traveling Salesman Problem. We consider a more general model that incorporates the actual cost in terms of gas prices. We have a vehicle with a given tank capacity. We assume that at each vertex gas may be purchased at a certain price. The objective is to find the cheapest route to go from s to t, or the cheapest tour visiting a given set of locations. Surprisingly, the problem of find the cheapest way to go from s to t can be solved in polynomial time and is not NP-complete. For most other versions however, the problem is NP-complete and we develop polynomial time approximation algorithms for these versions.
Research supported by NSF grant CCF-0430650. Full version available at http://www.cs.umd.edu/~samir/grant/esa07.ps

Contact Information Samir Khuller
Email: samir@cs.umd.edu

Contact Information Azarakhsh Malekian
Email: malekian@cs.umd.edu

Contact Information Julián Mestre
Email: jmestre@cs.umd.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.112 • Server: mpweb05
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)