TY - GEN
T1 - A divide and conquer algorithm for d-dimensional arrangement
AU - Charikar, Moses
AU - Makarychev, Konstantin
AU - Makarychev, Yury
N1 - Funding Information:
http://www.cs.princeton.edu/~moses/Supported by NSF ITR grant CCR-0205594, NSF CAREER award CCR-0237113, MSPA-MCS award 0528414, and an Alfred P. Sloan Fellowship. http://www.cs.princeton.edu/~kmakaryc/ Supported by a Gordon Wu fellowship. http://www.cs.princeton.edu/~ymakaryc/ Supported by a Gordon Wu fellowship.
Publisher Copyright:
Copyright © 2007 by the Association for Computing Machinery, Inc. and the Society for Industrial and Applied Mathematics.
PY - 2007
Y1 - 2007
N2 - We give an O(√log n)-approximation algorithm for d-dimensional arrangement - the problem of mapping a graph to a d-dimensional grid (for constant d ≥ 2) to minimize the sum of edge lengths. This improves the previous best O(log n log log n) approximation of Even, Naor, Rao and Schieber. The d = 1 case is the well studied Minimum Linear Arrangement problem. The problem is equivalent to the question of mapping a graph to integer points on a line so as to minimize the sum of edge costs, where edge costs are measured by edge lengths raised to the exponent α = 1/d. We give a simple recursive partitioning algorithm for this variant of linear arrangement for any exponent α ∈ (0, 1). Our analysis also applies to a directed version of the problem: given a directed graph, the goal is to map vertices to the line so as to minimize the sum of costs of forward edges. As before, edge costs are edge lengths raised to the exponent α. The α = 0 case is the well known Minimum Feedback Arc Set problem, and the α = 1 case is essentially the Minimum Storage-Time Product problem. We analyze an extremely simple divide and conquer algorithm that uses a balanced cut subroutine with approximation ratio β to recursively partition the graph. Our analysis shows that this approach gives an approximation ratio of O(β) for the minimum linear arrangement problem with exponent α for any fixed α ∈ (0, 1).
AB - We give an O(√log n)-approximation algorithm for d-dimensional arrangement - the problem of mapping a graph to a d-dimensional grid (for constant d ≥ 2) to minimize the sum of edge lengths. This improves the previous best O(log n log log n) approximation of Even, Naor, Rao and Schieber. The d = 1 case is the well studied Minimum Linear Arrangement problem. The problem is equivalent to the question of mapping a graph to integer points on a line so as to minimize the sum of edge costs, where edge costs are measured by edge lengths raised to the exponent α = 1/d. We give a simple recursive partitioning algorithm for this variant of linear arrangement for any exponent α ∈ (0, 1). Our analysis also applies to a directed version of the problem: given a directed graph, the goal is to map vertices to the line so as to minimize the sum of costs of forward edges. As before, edge costs are edge lengths raised to the exponent α. The α = 0 case is the well known Minimum Feedback Arc Set problem, and the α = 1 case is essentially the Minimum Storage-Time Product problem. We analyze an extremely simple divide and conquer algorithm that uses a balanced cut subroutine with approximation ratio β to recursively partition the graph. Our analysis shows that this approach gives an approximation ratio of O(β) for the minimum linear arrangement problem with exponent α for any fixed α ∈ (0, 1).
UR - http://www.scopus.com/inward/record.url?scp=84902075660&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84902075660&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84902075660
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 541
EP - 546
BT - Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
PB - Association for Computing Machinery
T2 - 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
Y2 - 7 January 2007 through 9 January 2007
ER -