Portal de Periódicos da CAPES

An improved approximation ratio for the minimum linear arrangement problem

2006; Elsevier BV; Volume: 101; Issue: 1 Linguagem: Inglês

10.1016/j.ipl.2006.07.009

1872-6119

Uriel Feige, James R. Lee,

Algorithms and Data Compression

We observe that combining the techniques of Arora, Rao, and Vazirani, with the rounding algorithm of Rao and Richa yields an O(lognloglogn)-approximation for the minimum-linear arrangement problem. This improves over the O(logn)-approximation of Rao and Richa.