An improved approximation ratio for the minimum linear arrangement problem

DOI10.1016/J.IPL.2006.07.009MaRDI QIDQ845884zbMATH OpenOpenAlexFDO

Authors James R. Lee, Uriel Feige

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)

Recommendations

• Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues
• scientific article; zbMATH DE number 1617262
• Approximation algorithms for maximum linear arrangement
• Tractable parameterizations for the minimum linear arrangement problem
• Tractable parameterizations for the minimum linear arrangement problem
• A compact quadratic model and linearizations for the minimum linear arrangement problem
• A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem
• Approximating Minimum Linear Ordering Problems
• Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems

Cites work

• l²₂ spreading metrics for vertex ordering problems
• Divide-and-conquer approximation algorithms via spreading metrics
• Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
• Euclidean distortion and the sparsest cut (extended abstract)
• Excluded minors, network decomposition, and multicommodity flow
• Expander flows, geometric embeddings and graph partitioning
• New Approximation Techniques for Some Linear Ordering Problems
• On distance scales, embeddings, and efficient relaxations of the cut cone

Cited in

(25)

• Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs
• Distributed balanced partitioning via linear embedding
• On an ordering problem in weighted hypergraphs
• Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges
• Approximation algorithms for maximum linear arrangement
• Convex relaxations for permutation problems
• \(\ell ^2_2\) spreading metrics for vertex ordering problems
• A correction on Shiloach's algorithm for minimum linear arrangement of trees
• A divide and conquer algorithm for \(d\)-dimensional arrangement
• On a class of metrics related to graph layout problems
• \(d\)-dimensional arrangement revisited
• A New Lower Bound for the Minimum Linear Arrangement of a Graph
• Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues
• Low-light trees, and tight lower bounds for Euclidean spanners
• New Approximation Techniques for Some Linear Ordering Problems
• Improved approximation algorithms for the Min-Max selecting items problem
• Demand-aware network designs of bounded degree
• scientific article; zbMATH DE number 1670654 (Why is no real title available?)
• Mildly Exponential Time Approximation Algorithms for Vertex Cover, Balanced Separator and Uniform Sparsest Cut
• Minimum Linear Arrangement of Series-Parallel Graphs
• Hardness and approximation of submodular minimum linear ordering problems
• Approximation guarantees for the minimum linear arrangement problem by higher eigenvalues
• scientific article; zbMATH DE number 1617262 (Why is no real title available?)
• On a binary distance model for the minimum linear arrangement problem
• A variation on the min cut linear arrangement problem

This page was built for publication: An improved approximation ratio for the minimum linear arrangement problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q845884)