Minimum d-dimensional arrangement with fixed points

n 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 ℤ^d (for some fixed dimension d ≥ 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 k 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 · logn)-approximation algorithm, based on a strengthening of the spreading-metric LP for 2-dimAP. The integrality gap for this LP is shown to be Ω(k^1/4). We also show that it is NP-hard to approximate 2-DIMAP+ within a factor better than Ω(k^1/4–∊). We also consider a (conceptually harder, but practically even more interesting) variant of 2-dimAP+, where the target space is the grid , instead of the entire integer lattice ℤ². For this problem, we obtain a O(klogklogn)-approximation using the same LP relaxation. We complement this upper bound by showing an integrality gap of Ω(k^1/2), and an Ω(k^1/2–∊)-inapproximability result.

Our results naturally extend to the case of arbitrary fixed target dimension d ≥ 1.