Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:


URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 05:52:20 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section