Engineering Weighted Connectivity Augmentation Algorithms
<|reference_start|>Engineering Weighted Connectivity Augmentation Algorithms: Increasing the connectivity of a graph is a pivotal challenge in robust network design. The weighted connectivity augmentation problem is a common version of the problem that takes link costs into consideration. The problem is then to find a minimum cost subset of a given set of weighted links that increases the connectivity of a graph by one when the links are added to the edge set of the input instance. In this work, we give a first implementation of recently discovered better-than-2 approximations. Furthermore, we propose three new heuristic and one exact approach. These include a greedy algorithm considering link costs and the number of unique cuts covered, an approach based on minimum spanning trees and a local search algorithm that may improve a given solution by swapping links of paths. Our exact approach uses an ILP formulation with efficient cut enumeration as well as a fast initialization routine. We then perform an extensive experimental evaluation which shows that our algorithms are faster and yield the best solutions compared to the current state-of-the-art as well as the recently discovered better-than-2 approximation algorithms. Our novel local search algorithm can improve solution quality even further.<|reference_end|>
@article{faraj2024engineering,
    title={Engineering Weighted Connectivity Augmentation Algorithms},
    author={Marcelo Fonseca Faraj, Ernestine Gro{ss}mann, Felix Joos, Thomas
  M"oller, Christian Schulz},
    journal={arXiv preprint arXiv:2402.07753},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.07753},
    primaryClass={cs.DS}
}