Finite termination of min-sum auction I for unique maximum weight matchings

From papers

Let π\pi^* denote the maximum weight matching, and consider the min-sum auction I algorithm, whose step (4) includes the condition

m~αijβjkm~βjαik1.\tilde{m}_{\alpha_{i_j}\rightarrow\beta_j}^k \geq \tilde{m}_{\beta_j\rightarrow\alpha_i}^{k-1}.

Finite-termination conjecture. If π\pi^* is unique, then the min-sum auction I algorithm terminates after finitely many iterations when this condition is removed from step (4).

The conjecture concerns whether uniqueness of the maximum weight matching suffices for finite termination of the modified algorithm. The source reports simulation evidence supporting it, but provides no proof or resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Mohsen Bayati, Devavrat Shah and Mayank Sharma, “Maximum Weight Matching via Max-Product Belief Propagation”, arXiv:cs/0508101 (2007).

Solutions 0

No solutions have been posted yet.