3 papers
cs.DS2025
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…
cs.DM2024
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…
cs.DM2024
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 assumptions on the graph. The Glauber dynamic…