Approximation algorithms for maximum linear arrangement

The GENERALIZED MAXIMUM LINEAR ARRANGEMENT PROBLEM is to compute for a given vector x is an element of R-n and an n x n non-negative symmetric matrix W = (w(i,j)), a permutation pi of {1,..., n) that maximizes Sigma (i,j) w(pii,pij) \x(j) - x(i)\. We present a fast 1/3-approximation algorithm for the problem. We present a randomized approximation algorithm with a better performance guarantee for the special case where x(i) = i, i = 1,..., n. Finally, we introduce a 1/2-approximation algorithm for MAX k-CUT WITH GIVEN SIZES OF PARTS. This matches the bound obtained by Ageev and Sviridenko, but without using linear programming. (C) 2001 Elsevier Science B.V. All rights reserved.