License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.187
URN: urn:nbn:de:0030-drops-53032
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5303/
Go to the corresponding LIPIcs Volume Portal

Chuzhoy, Julia ; Kim, David H. K.

On Approximating Node-Disjoint Paths in Grids

pdf-format:
13.pdf (2 MB)

Abstract

In the Node-Disjoint Paths (NDP) problem, the input is an undirected n-vertex graph G, and a collection {(s_1,t_1),...,(s_k,t_k)} of pairs of vertices called demand pairs. The goal is to route the largest possible number of the demand pairs (s_i,t_i), by selecting a path connecting each such pair, so that the resulting paths are node-disjoint. NDP is one of the most basic and extensively studied routing problems. Unfortunately, its approximability is far from being well-understood: the best current upper bound of O(sqrt(n)) is achieved via a simple greedy algorithm, while the best current lower bound on its approximability is Omega(log^{1/2-\delta}(n)) for any constant delta. Even for seemingly simpler special cases, such as planar graphs, and even grid graphs, no better approximation algorithms are currently known. A major reason for this impasse is that the standard technique for designing approximation algorithms for routing problems is LP-rounding of the standard multicommodity flow relaxation of the problem, whose integrality gap for NDP is Omega(sqrt(n)) even on grid graphs.

Our main result is an O(n^{1/4} * log(n))-approximation algorithm for NDP on grids. We distinguish between demand pairs with both vertices close to the grid boundary, and pairs where at least one of the two vertices is far from the grid boundary. Our algorithm shows that when all demand pairs are of the latter type, the integrality gap of the multicommodity flow LP-relaxation is at most O(n^{1/4} * log(n)), and we deal with demand pairs of the former type by other methods. We complement our upper bounds by proving that NDP is APX-hard on grid graphs.

BibTeX - Entry

@InProceedings{chuzhoy_et_al:LIPIcs:2015:5303,
  author =	{Julia Chuzhoy and David H. K. Kim},
  title =	{{On Approximating Node-Disjoint Paths in Grids}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{187--211},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5303},
  URN =		{urn:nbn:de:0030-drops-53032},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.187},
  annote =	{Keywords: Node-disjoint paths, approximation algorithms, routing and layout}
}

Keywords: Node-disjoint paths, approximation algorithms, routing and layout
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI