DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2024.56

A Simple Deterministic Near-Linear Time Approximation Scheme for Transshipment with Arbitrary Positive Edge Costs

Authors: Emily Fox

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract

We describe a simple deterministic near-linear time approximation scheme for uncapacitated minimum cost flow in undirected graphs with positive real edge weights, a problem also known as transshipment. Specifically, our algorithm takes as input a (connected) undirected graph G = (V, E), vertex demands b ∈ R^V such that ∑_{v ∈ V} b(v) = 0, positive edge costs c ∈ R_{> 0}^E, and a parameter ε > 0. In O(ε^{-2} m log^{O(1)} n) time, it returns a flow f such that the net flow out of each vertex is equal to the vertex’s demand and the cost of the flow is within a (1 + ε) factor of optimal. Our algorithm is combinatorial and has no running time dependency on the demands or edge costs. With the exception of a recent result presented at STOC 2022 for polynomially bounded edge weights, all almost- and near-linear time approximation schemes for transshipment relied on randomization to embed the problem instance into low-dimensional space. Our algorithm instead deterministically approximates the cost of routing decisions that would be made if the input were subject to a random tree embedding. To avoid computing the Ω(n²) vertex-vertex distances that an approximation of this kind suggests, we also take advantage of the clustering method used in the well-known Thorup-Zwick distance oracle.

Cite as

Emily Fox. A Simple Deterministic Near-Linear Time Approximation Scheme for Transshipment with Arbitrary Positive Edge Costs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fox:LIPIcs.ESA.2024.56,
  author =	{Fox, Emily},
  title =	{{A Simple Deterministic Near-Linear Time Approximation Scheme for Transshipment with Arbitrary Positive Edge Costs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.56},
  URN =		{urn:nbn:de:0030-drops-211270},
  doi =		{10.4230/LIPIcs.ESA.2024.56},
  annote =	{Keywords: Transshipment, minimum cost flow, approximation algorithms}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2024.58

Fréchet Edit Distance

Authors: Emily Fox, Amir Nayyeri, Jonathan James Perry, and Benjamin Raichel

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

We define and investigate the Fréchet edit distance problem. Given two polygonal curves π and σ and a threshhold value δ > 0, we seek the minimum number of edits to σ such that the Fréchet distance between the edited σ and π is at most δ. For the edit operations we consider three cases, namely, deletion of vertices, insertion of vertices, or both. For this basic problem we consider a number of variants. Specifically, we provide polynomial time algorithms for both discrete and continuous Fréchet edit distance variants, as well as hardness results for weak Fréchet edit distance variants.

Cite as

Emily Fox, Amir Nayyeri, Jonathan James Perry, and Benjamin Raichel. Fréchet Edit Distance. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.SoCG.2024.58,
  author =	{Fox, Emily and Nayyeri, Amir and Perry, Jonathan James and Raichel, Benjamin},
  title =	{{Fr\'{e}chet Edit Distance}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{58:1--58:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.58},
  URN =		{urn:nbn:de:0030-drops-200032},
  doi =		{10.4230/LIPIcs.SoCG.2024.58},
  annote =	{Keywords: Fr\'{e}chet distance, Edit distance, Hardness}
}

Search Results

Documents authored by Fox, Emily

A Simple Deterministic Near-Linear Time Approximation Scheme for Transshipment with Arbitrary Positive Edge Costs

Abstract

Cite as

Fréchet Edit Distance

Abstract

Cite as

Thanks for your feedback!

Could not send message