TY - GEN

T1 - Minimum d-dimensional arrangement with fixed points

AU - Gupta, Anupam

AU - Sidiropoulos, Anastasios

PY - 2014

Y1 - 2014

N2 - 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 Zd (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-DlMAP, 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-DlMAP+, 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(k1/2 · 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 Ω(k1/4). We also show that it is NP-hard to approximate 2-DIMAP+ within a factor better than Ω(k1/4-ε). We also consider a (conceptually harder, but practically even more interesting) variant of 2-DIMAP+, where the target space is the grid Z√ n Z√ n, instead of the entire integer lattice Z2. For this problem, we obtain a O(klog k log n)- Approximation using the same LP relaxation. We com-plement this upper bound by showing an integrality gap of Ω(k1/2), and an Ω(k 1/2-ε)-iniapproximability result. Our results naturally extend to the case of arbitrary fixed target dimension d ≥ 1.

AB - 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 Zd (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-DlMAP, 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-DlMAP+, 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(k1/2 · 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 Ω(k1/4). We also show that it is NP-hard to approximate 2-DIMAP+ within a factor better than Ω(k1/4-ε). We also consider a (conceptually harder, but practically even more interesting) variant of 2-DIMAP+, where the target space is the grid Z√ n Z√ n, instead of the entire integer lattice Z2. For this problem, we obtain a O(klog k log n)- Approximation using the same LP relaxation. We com-plement this upper bound by showing an integrality gap of Ω(k1/2), and an Ω(k 1/2-ε)-iniapproximability result. Our results naturally extend to the case of arbitrary fixed target dimension d ≥ 1.

UR - http://www.scopus.com/inward/record.url?scp=84902105496&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902105496&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973402.125

DO - 10.1137/1.9781611973402.125

M3 - Conference contribution

AN - SCOPUS:84902105496

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1727

EP - 1738

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

Y2 - 5 January 2014 through 7 January 2014

ER -