  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 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.
  A special case of the problem called NDP-Grid, where the underlying graph is
a grid, has been studied extensively. The best current approximation algorithm
for NDP-Grid achieves an $\tilde{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 sub-graph of a grid, and all source vertices lie on the
grid boundary. In a follow-up work, the authors further show that NDP-Grid 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 NDP-Grid, 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} \cdot \log\log n)}$-approximation algorithm for this
problem. We generalize this result to instances where the source vertices lie
within a prescribed distance from the grid boundary.
  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. 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.

Data Structures and Algorithms