  In the Minimum $d$-Dimensional Arrangement Problem (d-dimAP) we are given a
graph with edge weights, and the goal is to find a 1-1 map of the vertices into
$\mathbb{Z}^d$ (for some fixed dimension $d\geq 1$) minimizing the total
weighted stretch of the edges. This problem arises in VLSI placement and chip
design.
  Motivated by these applications, we consider a generalization of d-dimAP,
where the positions of some of the vertices (pins) is fixed and specified as
part of the input. We are asked to extend this partial map to a map of all the
vertices, again minimizing the weighted stretch of edges. This generalization,
which we refer to as d-dimAP+, arises naturally in these application domains
(since it can capture blocked-off parts of the board, or the requirement of
power-carrying pins to be in certain locations, etc.). Perhaps surprisingly,
very little is known about this problem from an approximation viewpoint.
  For dimension $d=2$, we obtain an $O(k^{1/2} \cdot \log n)$-approximation
algorithm, based on a strengthening of the spreading-metric LP for 2-dimAP. The
integrality gap for this LP is shown to be $\Omega(k^{1/4})$. We also show that
it is NP-hard to approximate 2-dimAP+ within a factor better than
$\Omega(k^{1/4-\eps})$. We also consider a (conceptually harder, but
practically even more interesting) variant of 2-dimAP+, where the target space
is the grid $\mathbb{Z}_{\sqrt{n}} \times \mathbb{Z}_{\sqrt{n}}$, instead of
the entire integer lattice $\mathbb{Z}^2$. For this problem, we obtain a $O(k
\cdot \log^2{n})$-approximation using the same LP relaxation. We complement
this upper bound by showing an integrality gap of $\Omega(k^{1/2})$, and an
$\Omega(k^{1/2-\eps})$-inapproximability result.
  Our results naturally extend to the case of arbitrary fixed target dimension
$d\geq 1$.
