Weighted uniform-edge conjecture for random bipartite matchings

Let A=(aij)A=(a_{ij}) be a doubly stochastic n×nn\times n matrix, and let W=(wij)W=(w_{ij}) be a matrix of edge weights satisfying

i,j=1nwijaij=1.\sum_{i,j=1}^{n}w_{ij}a_{ij}=1.

Let RR be the random bipartite graph in which edge (i,j)(i,j) appears independently with probability aija_{ij}. Weighted uniform-edge conjecture. The expected weight of a maximum-weight matching in RR is minimized when aij=wij=1/na_{ij}=w_{ij}=1/n for every (i,j)(i,j). This weighted form is motivated by the duality between contention-resolution schemes and expected matching quantities; proving it would yield an optimal γ\gamma-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

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.