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 -