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?