0

I have a list of clustered points but they are not in the cluster which has the center closest to them. The objective is to reassign them to minimize the total distance of each point to its cluster center.

All the points can not be reassigned individually since there's a constraint on cluster size, and moving any of these points individually would cause a violation.

So it's only possible to reassign them in pairs or groups. I want to build a potential assignment graph G=(V, E) with all the points.

There could be one or more closer clusters than the point's current cluster, so besides a pair swap between two clusters there could be a group reassignment across three or more clusters.

If I can get a proper represented graph, I could identify possible assignment by searching strongly-connected-components. But I'm not sure how to construct the graph to find the points that is guaranteed to decrease the objective. Any thoughts are appreciated! Thanks

I'm not sure if there's enough information for you to answer. There's a distance matrix for all the points to all cluster centers. Or if anything else needed, please let me know.

Improve this question
5
  • 1
    @qshngv each Stack Exchange site has its particular focus described in the help center. Programmers.SE has a community more of the... industry programmers and architects than the theoreticians and academics (though they're here too). CS.SE, on the other hand, the ratios are reversed. When you start asking about the findings of academic papers, you might find CS.SE to have the community that can best answer this (not that we can't, but we may answer it quite differently than what you are looking for). Also note, you're kind of asking us to read a 23 page paper to answer your question. Commented May 4, 2015 at 22:07
  • Thanks for the explanation. I read the help center post and saw this bullet point algorithm and data structure concepts, that's why I decided to post my question here since I didn't get a response on CS.SE. Commented May 5, 2015 at 0:12
  • I added the link as a reference, because I thought maybe someone with more experience could understand the data structure from the paragraph quote I pasted in the post. I feel like it's detailed enough to describe the structure, but I couldn't interpret it because of my lack of experience. But maybe I was wrong. Anyways, thanks all for your time. If you know any recommendations on resources(books or websites) I could read on graph data structure, I'd also be appreciated. Commented May 5, 2015 at 0:12
  • 1
    @qshngv algorithms are on-topic on this site and we do help with conceptual programming questions. If you need help modeling or designing an algorithm in code then that is on-topic here, if you need help with the discrete math then CS.SE is the proper site. Regardless, you specifically stated "I'm new to programming and don't have experience with graph data structure." You really need to learn how to walk before you run, and you need to understand what different graphs are, how to model them in software, and their uses before you can tackle this problem. Commented May 5, 2015 at 2:13
  • 1
    Hi all, I edited my question more specifically. Much appreciated if you could take another look. Thanks! Commented May 5, 2015 at 14:25

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.