Polynomial-time convergence conjecture for non-increasing edge recoloring
Polynomial-time convergence conjecture for non-increasing edge recoloring
Let be the complete graph on vertices, and let be the potential function on colorings of with colors. Consider the process that starts from a random coloring, repeatedly chooses a random edge and a random color , and recolors to if this does not increase . Polynomial-time convergence conjecture. With probability , this process converges to a one-factorization of in time . The source presents this as a belief based on simulations and does not establish the claimed high-probability polynomial-time convergence.
Sources & referencesView supporting material
Primary source
Maya Dotan and Nati Linial, “Efficient Generation of One-Factorizations through Hill Climbing”, arXiv:1707.00477 (2017).
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.