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

About 3 years old · traced to

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.

References

Primary source

D Ellis Hershkowitz, Nathan Klein and Rico Zenklusen, “Ghost Value Augmentation for k-Edge-Connectivity”, arXiv:2311.09941 (2024).

Progress summary

Never refreshed

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.