DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2016.7

An Efficient Algorithm for Placing Electric Vehicle Charging Stations

Authors: Pankaj K. Agarwal, Jiangwei Pan, and Will Victor

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract

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 small-size subset H of vertices of G such that by placing charging stations at vertices in H, every shortest path in G becomes EV-feasible, 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 bi-criteria approximation algorithm with running time near-linear 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 EV-feasible path between two query vertices of G.

Cite as

Pankaj K. Agarwal, Jiangwei Pan, and Will Victor. An Efficient Algorithm for Placing Electric Vehicle Charging Stations. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 7:1-7:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.ISAAC.2016.7,
  author =	{Agarwal, Pankaj K. and Pan, Jiangwei and Victor, Will},
  title =	{{An Efficient Algorithm for Placing Electric Vehicle Charging Stations}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{7:1--7:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.7},
  URN =		{urn:nbn:de:0030-drops-67782},
  doi =		{10.4230/LIPIcs.ISAAC.2016.7},
  annote =	{Keywords: Shortest path hitting set, Charging station placement, Electric vehicle}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2016.6

Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences

Authors: Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract

We present the first subquadratic algorithms for computing similarity between a pair of point sequences in R^d, for any fixed d > 1, using dynamic time warping (DTW) and edit distance, assuming that the point sequences are drawn from certain natural families of curves. In particular, our algorithms compute (1 + eps)-approximations of DTW and ED in near-linear time for point sequences drawn from k-packed or k-bounded curves, and subquadratic time for backbone sequences. Roughly speaking, a curve is k-packed if the length of its intersection with any ball of radius r is at most kr, and it is k-bounded if the sub-curve between two curve points does not go too far from the two points compared to the distance between the two points. In backbone sequences, consecutive points are spaced at approximately equal distances apart, and no two points lie very close together. Recent results suggest that a subquadratic algorithm for DTW or ED is unlikely for an arbitrary pair of point sequences even for d = 1. The commonly used dynamic programming algorithms for these distance measures reduce the problem to computing a minimum-weight path in a grid graph. Our algorithms work by constructing a small set of rectangular regions that cover the grid vertices. The weights of vertices inside each rectangle are roughly the same, and we develop efficient procedures to compute the approximate minimum-weight paths through these rectangles.

Cite as

Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying. Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2016.6,
  author =	{Agarwal, Pankaj K. and Fox, Kyle and Pan, Jiangwei and Ying, Rex},
  title =	{{Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.6},
  URN =		{urn:nbn:de:0030-drops-58989},
  doi =		{10.4230/LIPIcs.SoCG.2016.6},
  annote =	{Keywords: Dynamic time warping, Edit distance, Near-linear-time algorithm, Dynamic programming, Well-separated pair decomposition}
}

Search Results

Documents authored by Pan, Jiangwei

An Efficient Algorithm for Placing Electric Vehicle Charging Stations

Abstract

Cite as

Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences

Abstract

Cite as

Thanks for your feedback!

Could not send message