Minimum d-dimensional arrangement with fixed points

Anupam Gupta, Anastasios Sidiropoulos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PublisherAssociation for Computing Machinery
Pages1727-1738
Number of pages12
ISBN (Print)9781611973389
DOIs
StatePublished - 2014
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
Duration: Jan 5 2014Jan 7 2014

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Country/TerritoryUnited States
CityPortland, OR
Period1/5/141/7/14

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Minimum d-dimensional arrangement with fixed points'. Together they form a unique fingerprint.

Cite this