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

About 21 years old · traced to

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

m~αij→βjk≥m~βj→αik−1.\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.