Your algorithm looks surprisingly similar to "Affinity Propagation" which uses message passing techniques to (approximately) optimize the binary integer programming problem. Message passing algorithms have always fascinated me as they seem to be related to deep structure in the original linear programming problem.

For example, there are results for other binary problems that show a relationship between fixed points of message passing and optimal dual points to the relaxed linear programming problem (see below for an example with maximum weighted independent sets).

Back in the day I spent a long time trying to directly relate the affinity propagation messages to a coordinate-descent type of algorithm on the dual for k-medoids but despite the similarity in structure I could never make it work.

I'm curious if you're familiar with this class of algorithms and how they compare (both practically and theoretically) to the work you've presented here? Thanks for sharing!

References: - https://www.science.org/doi/10.1126/science.1136800 - https://arxiv.org/abs/0807.5091