current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.
up vote 0 down vote favorite

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.

share|improve this question
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. –  MichaelT May 4 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. –  qshngv May 5 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. –  qshngv May 5 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. –  Snowman May 5 at 2:13
1  
Hi all, I edited my question more specifically. Much appreciated if you could take another look. Thanks! –  qshngv May 5 at 14:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.