Weighted uniform-edge conjecture for random bipartite matchings
Weighted uniform-edge conjecture for random bipartite matchings
Let be a doubly stochastic matrix, and let be a matrix of edge weights satisfying
Let be the random bipartite graph in which edge appears independently with probability . Weighted uniform-edge conjecture. The expected weight of a maximum-weight matching in is minimized when for every . This weighted form is motivated by the duality between contention-resolution schemes and expected matching quantities; proving it would yield an optimal -balanced contention-resolution scheme for bipartite matchings.
Sources & referencesView supporting material
Primary source
Pranav Nuti and Jan Vondrák, “Towards an Optimal Contention Resolution Scheme for Matchings”, arXiv:2211.03599 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.