CODEWITHSUNDEEP
algorithmapproximation
user3070752
user3070752

Reputation: 734

how to prove my approximation ratio?

suppose we are given a weighted graph G and we want to cluster its nodes into k clusters such that sum of weights of all edges between clusters be maximum. we want an approximation algorithm of ratio (1-1/k).

my solution : cause this is a maximization problem,first of all we must find an upper bound for OPT solution. let k be n and G is a complete graph so the OPT will be sum of all edges and its the maximum value we can reach to. so OPT <= SUM(all edges). the approach is described as :

if k = n the solution is trivial if k < n we consider all n node as a disjoint set and find the minimum weighted edge and union disjoint sets of two nodes which are connected through this edge. we repeat this procedure until number of disjoint sets equals to k.

at the end we have removed at least (n-k) low weighted edge (in this case our result equals to OPT) and at the worst case only (k-1) high weighted edge has been remained to bee added into the result. at this case result is Sum(k-1 high weighted edge). to prove that our approach has approximation ratio (1-1/k) we should show that (1-1/k)Sum(All) <= Sum(k-1 high weighted edge). I doubt this is correct or not.can any one help me to prove it?

Upvotes: 0

Views: 1079

Answers (2)

Mohammad
Mohammad

Reputation: 26

Let V1, ... , Vk be an initial random clustering on V with the same sizes. Now, it is sufficient that for each u in Vi and v in Vj with

W(u,Vi)+W(v,Vj) > W(u,Vj)+W(v,Vi)

move u to Vj and move v to Vi.

Now, we have:

https://i.sstatic.net/8zeTI.png

Upvotes: 1

Mohammad
Mohammad

Reputation: 26

Please let k=2 and then, run your proposed solution on the following graph :

G=(V,E) 

V={a,b,c,d} 

E={({a,b},2) , ({a,c},3) , ({a,d},1) , ({b,d},2000000) , ({c,d},2000000)}

Upvotes: 0

Related Questions