Approximation algorithms for maximum linear arrangement

The GENERALIZED MAXIMUM LINEAR ARRANGEMENT PROBLEM is to compute for a give n 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(p ii,pij) \x(j) - x(i)\. We present a fast 1/3-approximation algorithm for th e problem. We present a randomized approximation algorithm with a better pe rformance guarantee for the special case where x(i) = i, i = 1,..., n. Fina lly, we introduce a 1/2-approximation algorithm for MAX k-CUT WITH GIVEN SI ZES 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.