NeFut Logo NeFut
中 Admin Login

[CS.DS] Pairwise Reconnection for Cost-Distance Steiner Trees

Published at: 2026-11-09 22:00 Last updated: 2026-11-12 00:51
#algorithm #Tree #Graph

The Uniform Cost‑Distance Steiner Tree Problem asks for a rooted tree that minimizes the sum of edge costs and a weighted total of root‑to‑terminal distances. We design an algorithm that builds two candidate trees: one connects every terminal directly to the root, the other first pairs selected vertices and then attaches each pair to the root. The algorithm evaluates both trees and returns the one with the smaller objective value. The resulting randomized algorithm achieves an expected approximation factor of $1.698$ in the spanning‑tree case and $2.041$ in the general case, and it can be derandomized in polynomial time. The core of the pairwise‑matching analysis charges part of the augmentation cost directly to the connection and delay costs of an optimal solution, rather than only to the separated lower bound used in previous analyses. This allows the $1.698$ factor to fall below the maximum multiplicative gap $1+1/\sqrt{2}$ between the optimum value and that lower bound. We present families of instances that give a lower bound of $1+1/\sqrt{2}$ for cut‑and‑reconnect algorithms starting from a minimum spanning tree, and a lower bound approaching $3/2$ for our algorithm. Finally, we show that the Uniform Cost‑Distance Steiner Tree Problem and the Steiner‑tree version of the Cable‑Trench Problem are approximation‑equivalent up to an arbitrarily small additive loss.\n\nReview: The paper introduces a novel pairwise reconnection technique that substantially improves approximation guarantees for cost‑distance Steiner trees, and the derandomizable polynomial‑time algorithm broadens its practical relevance to related network design problems.

Original Source: https://arxiv.org/abs/2611.09374

[h] Back to Home