An improved approximation ratio for the minimum linear arrangement problem

DOI10.1016/j.ipl.2006.07.009zbMath1185.68856OpenAlexW2007525305MaRDI QIDQ845884

Uriel Feige, James R. Lee

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.07.009

zbMATH Keywords

approximation algorithms

Mathematics Subject Classification ID

Approximation algorithms (68W25)

Related Items

Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges ⋮ Minimum Linear Arrangement of Series-Parallel Graphs ⋮ Convex Relaxations for Permutation Problems ⋮ \(\ell ^2_2\) spreading metrics for vertex ordering problems ⋮ Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs ⋮ On a class of metrics related to graph layout problems ⋮ Demand-aware network designs of bounded degree ⋮ A New Lower Bound for the Minimum Linear Arrangement of a Graph ⋮ \(d\)-dimensional arrangement revisited ⋮ Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut ⋮ Distributed balanced partitioning via linear embedding ⋮ Low-light trees, and tight lower bounds for Euclidean spanners ⋮ On an ordering problem in weighted hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Divide-and-conquer approximation algorithms via spreading metrics
• Euclidean distortion and the sparsest cut
• l²₂ spreading metrics for vertex ordering problems
• New Approximation Techniques for Some Linear Ordering Problems
• Excluded minors, network decomposition, and multicommodity flow
• Expander flows, geometric embeddings and graph partitioning