Search Results

Documents authored by Carpenter, Timothy

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.14
Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion

Authors: Timothy Carpenter, Ario Salmasi, and Anastasios Sidiropoulos

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
The problem of routing in graphs using node-disjoint paths has received a lot of attention and a polylogarithmic approximation algorithm with constant congestion is known for undirected graphs [Chuzhoy and Li 2016] and [Chekuri and Ene 2013]. However, the problem is hard to approximate within polynomial factors on directed graphs, for any constant congestion [Chuzhoy, Kim and Li 2016]. Recently, [Chekuri, Ene and Pilipczuk 2016] have obtained a polylogarithmic approximation with constant congestion on directed planar graphs, for the special case of symmetric demands. We extend their result by obtaining a polylogarithmic approximation with constant congestion on arbitrary directed minor-free graphs, for the case of symmetric demands.
Cite as

Timothy Carpenter, Ario Salmasi, and Anastasios Sidiropoulos. Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{carpenter_et_al:LIPIcs.APPROX-RANDOM.2019.14,
  author =	{Carpenter, Timothy and Salmasi, Ario and Sidiropoulos, Anastasios},
  title =	{{Routing Symmetric Demands in Directed Minor-Free Graphs with Constant Congestion}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.14},
  URN =		{urn:nbn:de:0030-drops-112290},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.14},
  annote =	{Keywords: Routing, Node-disjoint, Symmetric demands, Minor-free graphs}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.21
Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces

Authors: Timothy Carpenter, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Anastasios Sidiropoulos

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We study the problem of finding a minimum-distortion embedding of the shortest path metric of an unweighted graph into a "simpler" metric X. Computing such an embedding (exactly or approximately) is a non-trivial task even when X is the metric induced by a path, or, equivalently, the real line. In this paper we give approximation and fixed-parameter tractable (FPT) algorithms for minimum-distortion embeddings into the metric of a subdivision of some fixed graph H, or, equivalently, into any fixed 1-dimensional simplicial complex. More precisely, we study the following problem: For given graphs G, H and integer c, is it possible to embed G with distortion c into a graph homeomorphic to H? Then embedding into the line is the special case H=K_2, and embedding into the cycle is the case H=K_3, where K_k denotes the complete graph on k vertices. For this problem we give - an approximation algorithm, which in time f(H)* poly (n), for some function f, either correctly decides that there is no embedding of G with distortion c into any graph homeomorphic to H, or finds an embedding with distortion poly(c); - an exact algorithm, which in time f'(H, c)* poly (n), for some function f', either correctly decides that there is no embedding of G with distortion c into any graph homeomorphic to H, or finds an embedding with distortion c. Prior to our work, poly(OPT)-approximation or FPT algorithms were known only for embedding into paths and trees of bounded degrees.
Cite as

Timothy Carpenter, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Anastasios Sidiropoulos. Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{carpenter_et_al:LIPIcs.SoCG.2018.21,
  author =	{Carpenter, Timothy and Fomin, Fedor V. and Lokshtanov, Daniel and Saurabh, Saket and Sidiropoulos, Anastasios},
  title =	{{Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{21:1--21:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.21},
  URN =		{urn:nbn:de:0030-drops-87344},
  doi =		{10.4230/LIPIcs.SoCG.2018.21},
  annote =	{Keywords: Metric embeddings, minimum-distortion embeddings, 1-dimensional simplicial complex, Fixed-parameter tractable algorithms, Approximation algorithms}
}
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