MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Khuller, Samir
Malekian, Azarakhsh
Mestre, Julián		dblp
dblp
dblp
Not MPG Author(s):
Khuller, Samir
Malekian, Azarakhsh
Editor(s):
Arge, Lars
Hoffmann, Michael
Welzl, Emo		dblp
dblp
dblp
Not MPII Editor(s):
Arge, Lars
Hoffmann, Michael
Welzl, Emo
BibTeX cite key*:
conf/esa/KhullerMM2007
Title, Booktitle
Title*:
To Fill or Not to Fill: The Gas Station Problem
Booktitle*:
15th Annual European Symposium on Algorithms
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Eilat, Israel
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
8 October 2007
Event End Date:
10 October 2007
Publisher
Name*:
Springer
URL:
Address*:
Berlin / Heidelberg
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
4698
Number:
Month:
Pages:
534-545
Year*:
2007
VG Wort Pages:
ISBN/ISSN:
978-3-540-75519-7
Sequence Number:
DOI:
10.1007/978-3-540-75520-3_48
Note, Abstract, ©
(LaTeX) 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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{conf/esa/KhullerMM2007,
AUTHOR = {Khuller, Samir and Malekian, Azarakhsh and Mestre, Juli{\'a}n},
 EDITOR = {Arge, Lars and Hoffmann, Michael and Welzl, Emo},
 TITLE = {To Fill or Not to Fill: The Gas Station Problem},
 BOOKTITLE = {15th Annual European Symposium on Algorithms},
 PUBLISHER = {Springer},
 YEAR = {2007},
 VOLUME = {4698},
 PAGES = {534--545},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Eilat, Israel},
 ISBN = {978-3-540-75519-7},
 DOI = {10.1007/978-3-540-75520-3_48},
}

Entry last modified by Julian Mestre, 02/16/2009
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Julian Mestre		Created
01/15/2008 17:52:20
Revisions
8.
7.
6.
5.
4.		Editor(s)
Julian Mestre
Julian Mestre
Julian Mestre
Julian Mestre
Julian Mestre		Edit Dates
02/16/2009 09:38:39 AM
02/16/2009 09:34:46 AM
02/07/2009 10:39:27 AM
06/04/2008 03:10:01 PM
06/04/2008 03:09:42 PM