An improved approximation ratio for the minimum linear arrangement problem

被引：44

作者：

Feige, Uriel

Lee, James R. ^{[1
]}

机构：

[1] Inst Adv Studies, Dept Math, Princeton, NJ USA

[2] Microsoft Res, Redmond, WA USA

[3] Weizmann Inst Sci, Dept Comp Sci & Appl Math, IL-76100 Rehovot, Israel

来源：

INFORMATION PROCESSING LETTERS | 2007年 / 101卷 / 01期

基金：

以色列科学基金会; 美国国家科学基金会;

关键词：

approximation algorithms;

D O I：

10.1016/j.ipl.2006.07.009

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We observe that combining the techniques of Arora, Rao, and Vazirani, with the rounding algorithm of Rao and Richa yields an O(root log n log log n)-approximation for the minimum-linear arrangement problem. This improves over the O (log n)-approximation of Rao and Richa. (c) 2006 Published by Elsevier B.V.

引用

页码：26 / 29

页数：4

共 8 条

[1]

[Anonymous], P 36 ANN ACM S THEOR

[2]

ARORA S, 2005, 37 ACM STOC, P553

[3]

Charikar M, 2006, P 17 ANN ACM SIAM S

[4]

Chawla S, 2005, PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P102

[5] Divide-and-conquer approximation algorithms via spreading metrics [J].

Even, G ;

Naor, J ;

Rao, S ;

Schieber, B .

JOURNAL OF THE ACM, 2000, 47 (04) :585-616

[6]

Klein P., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P682, DOI 10.1145/167088.167261

[7]

Lee JR, 2005, PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P92

[8] New approximation techniques for some linear ordering problems [J].

Rao, S ;

Richa, AW .

SIAM JOURNAL ON COMPUTING, 2004, 34 (02) :388-404

← 1 →