Priestley's conjecture on approximation for weighted k-edge-connected spanning multigraphs
Let be an edge-weighted graph, and let -ECSM denote the problem of finding a minimum-cost -edge-connected spanning multigraph, where edges may be used with arbitrary nonnegative integer multiplicity. An approximation algorithm is polynomial-time if its running time is polynomial in the input size.
Priestley's conjecture. -ECSM admits a polynomial-time -approximation algorithm.
For unweighted graphs, a -approximation is known, while the conjectured asymptotic dependence on for general edge weights was posed as an open question.
References
Primary source
D Ellis Hershkowitz, Nathan Klein and Rico Zenklusen, “Ghost Value Augmentation for k-Edge-Connectivity”, arXiv:2311.09941 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.