1

[2311.09941] Ghost Value Augmentation for $k$-ECSS and $k$-ECSM

 1 month ago
source link: https://arxiv.org/abs/2311.09941
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 16 Nov 2023 (v1), last revised 19 Nov 2023 (this version, v2)]

Ghost Value Augmentation for k-ECSS and k-ECSM

View PDF

We give a poly-time algorithm for the k-edge-connected spanning subgraph (k-ECSS) problem that returns a solution of cost no greater than the cheapest (k+10)-ECSS on the same graph. Our approach enhances the iterative relaxation framework with a new ingredient, which we call ghost values, that allows for high sparsity in intermediate problems.
Our guarantees improve upon the best-known approximation factor of 2 for k-ECSS whenever the optimal value of (k+10)-ECSS is close to that of k-ECSS. This is a property that holds for the closely related problem k-edge-connected spanning multi-subgraph (k-ECSM), which is identical to k-ECSS except edges can be selected multiple times at the same cost. As a consequence, we obtain a \left(1+O\left(\frac{1}{k}\right)\right)-approximation algorithm for k-ECSM, which resolves a conjecture of Pritchard and improves upon a recent \left(1+O\left(\frac{1}{\sqrt{k}}\right)\right)-approximation algorithm of Karlin, Klein, Oveis Gharan, and Zhang. Moreover, we present a matching lower bound for k-ECSM, showing that our approximation ratio is tight up to the constant factor in O\left(\frac{1}{k}\right), unless P=NP.
Subjects: Data Structures and Algorithms (cs.DS); Combinatorics (math.CO)
Cite as: arXiv:2311.09941 [cs.DS]
  (or arXiv:2311.09941v2 [cs.DS] for this version)
  https://doi.org/10.48550/arXiv.2311.09941

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK