Search Results

Documents authored by Chen, Da Qi

Found 3 Possible Name Variants:

Chen, Da Qi

Document
DOI: 10.4230/LIPIcs.SWAT.2020.5
Vertex Downgrading to Minimize Connectivity

Authors: Hassene Aissi, Da Qi Chen, and R. Ravi

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We consider the problem of interdicting a directed graph by deleting nodes with the goal of minimizing the local edge connectivity of the remaining graph from a given source to a sink. We introduce and study a general downgrading variant of the interdiction problem where the capacity of an arc is a function of the subset of its endpoints that are downgraded, and the goal is to minimize the downgraded capacity of a minimum source-sink cut subject to a node downgrading budget. This models the case when both ends of an arc must be downgraded to remove it, for example. For this generalization, we provide a bicriteria (4,4)-approximation that downgrades nodes with total weight at most 4 times the budget and provides a solution where the downgraded connectivity from the source to the sink is at most 4 times that in an optimal solution. We accomplish this with an LP relaxation and rounding using a ball-growing algorithm based on the LP values. We further generalize the downgrading problem to one where each vertex can be downgraded to one of k levels, and the arc capacities are functions of the pairs of levels to which its ends are downgraded. We generalize our LP rounding to get a (4k,4k)-approximation for this case.
Cite as

Hassene Aissi, Da Qi Chen, and R. Ravi. Vertex Downgrading to Minimize Connectivity. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{aissi_et_al:LIPIcs.SWAT.2020.5,
  author =	{Aissi, Hassene and Chen, Da Qi and Ravi, R.},
  title =	{{Vertex Downgrading to Minimize Connectivity}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{5:1--5:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.5},
  URN =		{urn:nbn:de:0030-drops-122527},
  doi =		{10.4230/LIPIcs.SWAT.2020.5},
  annote =	{Keywords: Vertex Interdiction, Vertex Downgrading, Network Interdiction, Approximation Algorithm}
}

Chen, Daniel

Document
DOI: 10.4230/OASIcs.ATMOS.2021.10
Fast Map Matching with Vertex-Monotone Fréchet Distance

Authors: Daniel Chen, Christian Sommer, and Daniel Wolleb

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract
We study a generalization for map matching algorithms that includes both geometric approaches such as the Fréchet distance and global weight approaches such as those typically used by Hidden Markov Models. Through this perspective, we discovered an efficient map matching algorithm with respect to the vertex-monotone Fréchet distance while using a heuristic tie-breaker inspired by global weight methods. While the classical Fréchet distance requires parameterizations to be monotone, the vertex-monotone Fréchet distance allows backtracking within edges. Our analysis and experimental evaluations show that relaxing the monotonicity constraint enables significantly faster algorithms without significantly altering the resulting map matched paths.
Cite as

Daniel Chen, Christian Sommer, and Daniel Wolleb. Fast Map Matching with Vertex-Monotone Fréchet Distance. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:OASIcs.ATMOS.2021.10,
  author =	{Chen, Daniel and Sommer, Christian and Wolleb, Daniel},
  title =	{{Fast Map Matching with Vertex-Monotone Fr\'{e}chet Distance}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{10:1--10:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.10},
  URN =		{urn:nbn:de:0030-drops-148794},
  doi =		{10.4230/OASIcs.ATMOS.2021.10},
  annote =	{Keywords: Fr\'{e}chet distance, map matching, minimum bottleneck path}
}

Chen, Danny Z.

Document
Complete Volume
DOI: 10.4230/LIPIcs.SoCG.2020
LIPIcs, Volume 164, SoCG 2020, Complete Volume

Authors: Sergio Cabello and Danny Z. Chen

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
LIPIcs, Volume 164, SoCG 2020, Complete Volume
Cite as

36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 1-1222, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@Proceedings{cabello_et_al:LIPIcs.SoCG.2020,
  title =	{{LIPIcs, Volume 164, SoCG 2020, Complete Volume}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{1--1222},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020},
  URN =		{urn:nbn:de:0030-drops-121576},
  doi =		{10.4230/LIPIcs.SoCG.2020},
  annote =	{Keywords: LIPIcs, Volume 164, SoCG 2020, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SoCG.2020.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Sergio Cabello and Danny Z. Chen

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 0:i-0:xx, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.SoCG.2020.0,
  author =	{Cabello, Sergio and Chen, Danny Z.},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{0:i--0:xx},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.0},
  URN =		{urn:nbn:de:0030-drops-121587},
  doi =		{10.4230/LIPIcs.SoCG.2020.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.293
L_1 Shortest Path Queries among Polygonal Obstacles in the Plane

Authors: Danny Z. Chen and Haitao Wang

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
Given a point s and a set of h pairwise disjoint polygonal obstacles with a total of n vertices in the plane, after the free space is triangulated, we present an O(n+h log h) time and O(n) space algorithm for building a data structure (called shortest path map) of size O(n) such that for any query point t, the length of the L_1 shortest obstacle-avoiding path from s to t can be reported in O(log n) time and the actual path can be found in additional time proportional to the number of edges of the path. Previously, the best algorithm computes such a shortest path map in O(n log n) time and O(n) space. In addition, our techniques also yield an improved algorithm for computing the L_1 geodesic Voronoi diagram of m point sites among the obstacles.
Cite as

Danny Z. Chen and Haitao Wang. L_1 Shortest Path Queries among Polygonal Obstacles in the Plane. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 293-304, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.STACS.2013.293,
  author =	{Chen, Danny Z. and Wang, Haitao},
  title =	{{L\underline1 Shortest Path Queries among Polygonal Obstacles in the Plane}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{293--304},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.293},
  URN =		{urn:nbn:de:0030-drops-39425},
  doi =		{10.4230/LIPIcs.STACS.2013.293},
  annote =	{Keywords: computational geometry, shortest path queries, shortest paths among obstacles, \$L\underline1\$/\$L\underlineinfty\$/rectilinear metric, shortest path maps, geodesic Vorono}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact