Finite termination of min-sum auction I for unique maximum weight matchings
Finite termination of min-sum auction I for unique maximum weight matchings
Let denote the maximum weight matching, and consider the min-sum auction I algorithm, whose step (4) includes the condition
Finite-termination conjecture. If 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
Sign in to submit a solution.
No solutions have been posted yet.