Paper Info
Title
Efficiently list-edge coloring multigraphs asymptotically optimally.
Abstract
We give polynomial time algorithms for the seminal results of Kahn, who showed that the Goldberg-Seymour and List-Coloring conjectures for (list-)edge coloring multigraphs hold asymptotically. Kahnu0027s arguments are based on the probabilistic method and are non-constructive. Our key insight is to show that the main result of Achlioptas, Iliopoulos and Kolmogorov for analyzing local search algorithms can be used to make constructive applications of a powerful version of the so-called Lopsided Lovasz Local Lemma. In particular, we use it to design algorithms that exploit the fact that correlations in the probability spaces on matchings used by Kahn decay with distance.
Year
DOI
Venue
2020
10.5555/3381089.3381231
SODA '20: ACM-SIAM Symposium on Discrete Algorithms Salt Lake City Utah January, 2020
Field
DocType
Volume
Discrete mathematics,Combinatorics,Computer science,List edge-coloring
Conference
abs/1812.10309
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Fotis Iliopoulos1135.28
Alistair Sinclair21506308.40