Priestley's conjecture on approximation for weighted k-edge-connected spanning multigraphs
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
D Ellis Hershkowitz, Nathan Klein and Rico Zenklusen, “Ghost Value Augmentation for k-Edge-Connectivity”, arXiv:2311.09941 (2024).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.