Priestley's conjecture on approximation for weighted k-edge-connected spanning multigraphs

From papers

Let G=(V,E)G=(V,E) be an edge-weighted graph, and let kk-ECSM denote the problem of finding a minimum-cost kk-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. kk-ECSM admits a polynomial-time (1+O(1/k))(1+O(1/k))-approximation algorithm.

For unweighted graphs, a (1+2/k)(1+2/k)-approximation is known, while the conjectured asymptotic dependence on kk 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

No solutions have been posted yet.