To fill or not to fill: The gas station problem

Samir Khuller*, Azarakhsh Malekian, Julián Mestre

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

38 Scopus citations


In this article 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 froms to t, or the cheapest tour visiting a given set of locations. We show that the problem of finding a cheapest plan to go from s to t can be solved in polynomial time. For most other versions, however, the problem is NP-complete and we develop polynomial-time approximation algorithms for these versions.

Original languageEnglish (US)
Article number36
JournalACM Transactions on Algorithms
Issue number3
StatePublished - Jul 1 2011


  • Approximation algorithms
  • Graph theory
  • Shortest paths
  • Vehicle routing

ASJC Scopus subject areas

  • Mathematics (miscellaneous)

Fingerprint Dive into the research topics of 'To fill or not to fill: The gas station problem'. Together they form a unique fingerprint.

Cite this