Efficiently list-edge coloring multigraphs asymptotically optimally

We give polynomial time algorithms for the seminal results of Kahn [22,23], who showed that the Goldberg-Seymour and List-Coloring conjectures for (list-)edge coloring multigraphs hold asymptotically. Kahn's arguments are based on the probabilistic method and are non-constructive. Our key insight is that we can combine sophisticated techniques due to Achlioptas, Iliopoulos and Kolmogorov [2] for the analysis of local search algorithms with correlation decay properties of the probability spaces on matchings used by Kahn in order to construct efficient edge-coloring algorithms.