# How to order objects to minimize non-adjacency cost

I have an array of $N$ objects, each appearing exactly once. I also have a list of $M$ pairs of the objects. Each pair has a "non-adjacency cost" that must be paid if the two objects are not adjacent in the array. Is there an algorithm that orders the object array to minimize the total cost?

The costs will change from time to time, so I'd like to be able to apply the algorithm iteratively. It doesn't have to produce an optimal solution, but should converge to one if the costs remain constant over enough iterations. Practically, I will have somewhere around 1,000,000 objects, and each object will be a member of about 5 pairs.

Here is what I have tried:

1. Combine pairs that refer to the same two objects by summing their cost.
2. Each iteration, find a random pair whose cost changed. If no costs changed, take a random pair.
3. For each of the two objects from the pair as obj1:
1. Set obj2 equal to the other object.
2. For each of the two objects touching obj1 as obj3:
1. Calculate the cost difference of swapping obj2 and obj3.
2. If it is less than zero, apply the swap and return.

I like my algorithm but it's pretty simple and I feel like it would fall on its face in select circumstances. Is there a better algorithm or some terminology I can google for?