4 papers
Hardness of Approximation for Shortest Path with Vector Costs
Charlie Carlson, Yury Makarychev, Ron Mosenzon
We obtain hardness of approximation results for the -Shortest Path problem, a variant of the classic Shortest Path problem with vector costs. For every integer $p \in [2,\i…
Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
Charlie Carlson, Xiaoyu Chen, Weiming Feng +1
We address the convergence rate of Markov chains for randomly generating an edge coloring of a given tree. Our focus is on the Glauber dynamics which updates the color at a randoml…
Flip Dynamics for Sampling Colorings: Improving Using a Simple Metric
Charlie Carlson, Eric Vigoda
We present improved bounds for randomly sampling -colorings of graphs with maximum degree ; our results hold without any further structural assumptions on the graph. The Glau…
Improved Distributed Algorithms for Random Colorings
Charlie Carlson, Daniel Frishberg, Eric Vigoda
We study distributed versions of Markov Chain Monte Carlo (MCMC) algorithms for generating random -colorings of an input graph with maximum degree . In the sequential setting…