1 Search Results for "Nimavat, Rachit"

Document

DOI: 10.4230/LIPIcs.ICALP.2018.38

Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary

Authors: Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

We study the classical Node-Disjoint Paths (NDP) problem: given an undirected n-vertex graph G, together with a set {(s_1,t_1),...,(s_k,t_k)} of pairs of its vertices, called source-destination, or demand pairs, find a maximum-cardinality set {P} of mutually node-disjoint paths that connect the demand pairs. The best current approximation for the problem is achieved by a simple greedy O(sqrt{n})-approximation algorithm. Until recently, the best negative result was an Omega(log^{1/2-epsilon}n)-hardness of approximation, for any fixed epsilon, under standard complexity assumptions. A special case of the problem, where the underlying graph is a grid, has been studied extensively. The best current approximation algorithm for this special case achieves an O~(n^{1/4})-approximation factor. On the negative side, a recent result by the authors shows that NDP is hard to approximate to within factor 2^{Omega(sqrt{log n})}, even if the underlying graph is a subgraph of a grid, and all source vertices lie on the grid boundary. In a very recent follow-up work, the authors further show that NDP in grid graphs is hard to approximate to within factor Omega(2^{log^{1-epsilon}n}) for any constant epsilon under standard complexity assumptions, and to within factor n^{Omega(1/(log log n)^2)} under randomized ETH. In this paper we study the NDP problem in grid graphs, where all source vertices {s_1,...,s_k} appear on the grid boundary. Our main result is an efficient randomized 2^{O(sqrt{log n}* log log n)}-approximation algorithm for this problem. Our result in a sense complements the 2^{Omega(sqrt{log n})}-hardness of approximation for sub-graphs of grids with sources lying on the grid boundary, and should be contrasted with the above-mentioned almost polynomial hardness of approximation of NDP in grid graphs (where the sources and the destinations may lie anywhere in the grid). Much of the work on approximation algorithms for NDP relies on the multicommodity flow relaxation of the problem, which is known to have an Omega(sqrt n) integrality gap, even in grid graphs, with all source and destination vertices lying on the grid boundary. Our work departs from this paradigm, and uses a (completely different) linear program only to select the pairs to be routed, while the routing itself is computed by other methods.

Cite as

Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chuzhoy_et_al:LIPIcs.ICALP.2018.38,
  author =	{Chuzhoy, Julia and Kim, David H. K. and Nimavat, Rachit},
  title =	{{Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.38},
  URN =		{urn:nbn:de:0030-drops-90423},
  doi =		{10.4230/LIPIcs.ICALP.2018.38},
  annote =	{Keywords: Node-disjoint paths, approximation algorithms, routing and layout}
}

Refine by Author
1 Chuzhoy, Julia
1 Kim, David H. K.
1 Nimavat, Rachit

Refine by Classification
1 Theory of computation → Routing and network design problems

Refine by Keyword
1 Node-disjoint paths
1 approximation algorithms
1 routing and layout

Refine by Type
1 document

Refine by Publication Year
1 2018

1 Search Results for "Nimavat, Rachit"

Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary

Abstract

Cite as

Thanks for your feedback!

Could not send message