To fill or not to fill: The gas station problem

Samir Khuller*, Azarakhsh Malekian, Julián Mestre

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

27 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationAlgorithms - ESA 2007 - 15th Annual European Symposium, Proceedings
Pages534-545
Number of pages12
StatePublished - Dec 1 2007
Event15th Annual European Symposium on Algorithms, ESA 2007 - Eilat, Israel
Duration: Oct 8 2007Oct 10 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4698 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th Annual European Symposium on Algorithms, ESA 2007
CountryIsrael
CityEilat
Period10/8/0710/10/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

    Khuller, S., Malekian, A., & Mestre, J. (2007). To fill or not to fill: The gas station problem. In Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings (pp. 534-545). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4698 LNCS).