1

The problem statement:
Give n variables and k pairs. The variables can be distinct by assigning a value from 1 to n to each variable. Each pair p contain 2 variables and let the absolute difference between 2 variables in p is abs(p). Define the upper bound of difference is U=max(Abs(p)|every p).

Find an assignment that minimize U.

Limit:   
n<=100  
k<=1000 

Each variable appear at least 2 times in list of pairs.

A problem instance:  
Input  
n=9, k=12  
1 2 (meaning pair x1 x2)   
1 3  
1 4  
1 5  
2 3  
2 6 
3 5   
3 7    
3 8  
3 9 
6 9  
8 9  
Output:  
1 2 5 4 3 6 7 8 9  
(meaning x1=1,x2=2,x3=5,...) 

Explaination: An assignment of x1=1,x2=2,x3=3,... will result in U=6 (3 9 has greastest abs value). The output assignment will get U=4, the minimum value (changed pair: 3 7 => 5 7, 3 8 => 5 8, etc. and 3 5 isn't changed. In this case, abs(p)<=4 for every pair).

There is an important point: To achieve the best assignments, the variables in the pairs that have greatest abs must be change.
Base on this, I have thought of a greedy algorithm:

1)Assign every x to default assignment (x(i)=i)  
2)Locate pairs that have largest abs and x(i)'s contained in them.  
3)For every i,j: Calculate U. Swap value of x(i),x(j). Calculate U'. If U'<U, stop and repeat step 3. If U'>=U for every i,j, end and output the assignment.  

However, this method has a major pitfall, if we need an assignment like this:

x(a)<<x(b), x(b)<<x(c), x(c)<<x(a)

, we have to swap in 2 steps, like: x(a)<=>x(b), then x(b)<=>x(c), then there is a possibility that x(b)<<x(a) in first step has its abs become larger than U and the swap failed.
Is there any efficient algorithm to solve this problem?

4

1 回答 1

2

This looks like http://en.wikipedia.org/wiki/Graph_bandwidth (NP complete, even for special cases). It looks like people run http://en.wikipedia.org/wiki/Cuthill-McKee_algorithm when they need to do this to try and turn a sparse matrix into a banded diagonal matrix.

于 2013-01-13T05:27:58.897 回答