Math @ Duke

Publications [#323822] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Pan, J; Victor, W, An efficient algorithm for placing electric vehicle charging stations,
LIPIcs, vol. 64
(December, 2016),
pp. 7.17.12, ISBN 9783959770262 [doi]
(last updated on 2018/02/22)
Abstract: © Pankaj K. Agarwal, Jiangwei Pan, and Will Victor. Motivated by the increasing popularity of electric vehicles (EV) and a lack of charging stations in the road network, we study the shortest path hitting set (SPHS) problem. Roughly speaking, given an input graph G, the goal is to compute a smallsize subset H of vertices of G such that by placing charging stations at vertices in H, every shortest path in G becomes EVfeasible, i.e., an EV can travel between any two vertices of G through the shortest path with a full charge. In this paper, we propose a bicriteria approximation algorithm with running time nearlinear in the size of G that has a logarithmic approximation on H and may require the EV to slightly deviate from the shortest path. We also present a data structure for computing an EVfeasible path between two query vertices of G.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

