An improved approximation ratio for the minimum linear arrangement problem
type: Item
instance of: scholarly article
title: An improved approximation ratio for the minimum linear arrangement problem
zbMATH Open document ID: 1185.68856
author: James R. Lee
author: Uriel Feige
published in: Information Processing Letters
publication date: 2010-01-29T00:00:00Z
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5664727
zbMATH Keywords: approximation algorithms
MaRDI profile type: Publication
full work available at URL: j.ipl.2006.07.009
OpenAlex ID: W2007525305
cites work: Euclidean distortion and the sparsest cut
cites work: Expander flows, geometric embeddings and graph partitioning
cites work: l22 spreading metrics for vertex ordering problems
cites work: Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut
cites work: Divide-and-conquer approximation algorithms via spreading metrics
cites work: Excluded minors, network decomposition, and multicommodity flow
cites work: On distance scales, embeddings, and efficient relaxations of the cut cone
cites work: New Approximation Techniques for Some Linear Ordering Problems
DOI: 10.1016/J.IPL.2006.07.009
Recommended article: Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues
Recommended article: Q2721982
Recommended article: Approximation algorithms for maximum linear arrangement
Recommended article: Tractable Parameterizations for the Minimum Linear Arrangement Problem
Recommended article: A compact quadratic model and linearizations for the minimum linear arrangement problem
Recommended article: A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem
Recommended article: Approximating Minimum Linear Ordering Problems
Recommended article: Improved Approximation Schemes for Linear Programming Relaxations of Combinatorial Optimization Problems
description: scientific article; zbMATH DE number 5664727