  Sublinear time complexity is required by the massively parallel computation
(MPC) model. Breaking dynamic programs into a set of sparse dynamic programs
that can be divided, solved, and merged in sublinear time.
  The rectangle escape problem (REP) is defined as follows: For $n$
axis-aligned rectangles inside an axis-aligned bounding box $B$, extend each
rectangle in only one of the four directions: up, down, left, or right until it
reaches $B$ and the density $k$ is minimized, where $k$ is the maximum number
of extensions of rectangles to the boundary that pass through a point inside
bounding box $B$. REP is NP-hard for $k>1$. If the rectangles are points of a
grid (or unit squares of a grid), the problem is called the square escape
problem (SEP) and it is still NP-hard.
  We give a $2$-approximation algorithm for SEP with $k\geq2$ with time
complexity $O(n^{3/2}k^2)$. This improves the time complexity of existing
algorithms which are at least quadratic. Also, the approximation ratio of our
algorithm for $k\geq 3$ is $3/2$ which is tight. We also give a
$8$-approximation algorithm for REP with time complexity $O(n\log n+nk)$ and
give a MPC version of this algorithm for $k=O(1)$ which is the first parallel
algorithm for this problem.
