[cicdw]

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

[ramraj07]

A 2 author science paper in 2007 for an algorithm. The authors ought to be proud indeed, this is close to the holy grail wet dream of mine (a single author original nature science paper; the only one I’ve seen in recent decades is the Nature paper on the purported active ingredient of royal jelly: royalactin https://www.nature.com/articles/nature10093 )

[motiwari]

Interesting, thanks for the references! I'm not too familiar with this line of work; let me read up on it and get back to you

[cicdw]

If you end up spending any time on this and finding anything interesting I'd love to know! My email address is in my profile, feel free to hit me up anytime; also happy to share any of my original notes, I'm pretty sure I have them TeXed up somewhere accessible.