2 papers
cs.DS2023
Revisiting Garg's 2-Approximation Algorithm for the k-MST Problem in Graphs
Emmett Breen, Renee Mirka, Zichen Wang +1
This paper revisits the 2-approximation algorithm for -MST presented by Garg in light of a recent paper of Paul et al.. In the -MST problem, the goal is to return a tree span…
math.OC2022
Graph Coloring and Semidefinite Rank
Renee Mirka, Devin Smedira, David P. Williamson
This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger, Motwani, and Sudan \cite{KMS98} give a vector program for which a colo…