Journal
INFORMATION PROCESSING LETTERS
Volume 80, Issue 4, Pages 171-177Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/S0020-0190(01)00159-4
Keywords
algorithms; algorithmical approximation
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available