TY - GEN

T1 - To fill or not to fill

T2 - 15th Annual European Symposium on Algorithms, ESA 2007

AU - Khuller, Samir

AU - Malekian, Azarakhsh

AU - Mestre, Julián

PY - 2007/12/1

Y1 - 2007/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=38049005518&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38049005518&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:38049005518

SN - 9783540755197

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 534

EP - 545

BT - Algorithms - ESA 2007 - 15th Annual European Symposium, Proceedings

Y2 - 8 October 2007 through 10 October 2007

ER -