Optimal improper vertex-coloring of graph with weighted edges

I have an undirected graph with weighted edges. I want to color the vertices with a given $$k$$ colors. Let's assume there is no proper coloring with $$k$$ colors such that adjacent nodes will always have different colors. I want to find the improper color assignments that would minimize the sum of weights of edges between nodes of the same color.

I have looked through many papers looking at improper coloring algorithms but cannot find this particular variant. This paper looks at something similar, but instead minimizes $$k$$ given a threshold on the sum of weights. Instead, I want to fix $$k$$ and minimize the sum of weights. Does anybody know the best approach for this?

Full citation to the paper:

J. Araujo, J.-C. Bermond, F. Giroire, F. Havet, D. Mazauric, R. Modrzejewski, Weighted improper coloring, Research report 7590, INRIA, Sophia Antipolis, 2011.

• Your problem is NP-hard. Are you interested in approximation algorithms? Heuristics? – Yuval Filmus Feb 26 at 21:12
• I think you should be able to use binary search on the threshold combined with the techniques of that paper, to get what you want. – D.W. Feb 26 at 21:15
• I would be fine with approximations or maybe a greedy algorithm if necessary. – Andy Carlson Feb 26 at 21:31
• Do you require some guarantees on the solution quality? Probably metaheuristics would be good on the problem, but can you clarify what you are hoping for more precisely? – Juho Feb 27 at 9:15