algorithm - Minimizing weighted sum

Question

I came across this problem quite recently. Suppose there are n points on x-axis, x[0],x[1] .. x[n-1]. Let the weight associated with each of these points be w[0],w[1] .. w[n-1]. Starting from any point between 0 to n-1, the objective is to cover all the points such that the sum of w[i]*d[i] is minimized where d[i] is the distance covered to reach the ith point from the starting point.

Example:
Suppose the points are: 1 5 10 20 40
Suppose the weights are: 1 2 10 50 13
If I choose to start at point 10 and choose to move to point 20 then to 5 then to 40 and then finally to 1, then the weighted sum will become 10*0+50*(10)+2*(10+15)+13*(10+15+35)+1*(10+15+35+39).

I have tried to solve it using greedy approach by starting off from the point which has maximum associated weight and move to second maximum weight point and so on. But the algorithm does not work. Can someone give me pointers about the approach which must be taken to solve this problem?

Answer 1

There's a very important fact that leads to a polynomial time algorithm:

Since the points are located on some axis, they generate a path graph, which means that for every 3 vertices v1,v2,v3, if v2 is between v1 and v3, then the distance between v1 and v3 equals the distance between v1 and v2 plus the distance between v2 and v3. therefor if for example we start at v1, the obj. function value of a path that goes first to v2 and then to v3 will always be less than the value of the path that first goes to v3 and then back to v2 because:

value of the first path = w[2]*D(v1,v2)+W[3]*(D(v1,v2)+D(v2,v3))

value of the second path = w[3]*D(v1,v3)+W[2]*((v1,v3)+D(v3,v2)) = w[3]*D(v1,v2)+w[3]*D(v2,v3)+w[2]*(D(v1,v2)+2*D(v3,v2))

If we subtract the first path value from the second, we are left with w[2]*2*D(v3,v2) which is equal to or greater than 0 unless you consider negative weights.

All this means that if we are located at a certain point, there are always only 2 options we should consider: going to closest unvisited point on the left or the closest unvisited point on the right.

This is very significant as it leaves us with 2^n possible paths rather than n! possible paths (like in the Travelling Salesman Problem).

Solving the TSP/minimum weight hamiltonian path on path graphs can be done in polynomial time using dynamic programming, you should apply the exact same method but modify the way you calculated the objective function.

Since you don't know the starting vertex, you'll have to run this algorithm n time, each time starting from a different vertex, which means the running time will be multiplied by n.