Approximation algorithms for network design problems
Éva Tardos, Vardges Melkonian · 2002
Survivable network design problems concern the design of those kind of networks that remain functional even if some of their elements (edges, nodes) are broken. Network design problems arise from many sources, including the design of various transportation systems as well as telephone and computer networks. The network design problems that we consider are NP-hard; so our goal is to find efficient approximation algorithms for them. While in the last 10 years there has been significant progress in designing approximation algorithms for undirected network design problems little progress has been made on their directed counterparts. The main goal of our work is to explain the difficulties intrinsic to directed networks and to give new algorithms for them. The specific problems we consider here are the network design with crossing supermodular demand and the strong connectivity problem. The main algorithms we design for these problems are the linear programming rounding algorithm, the primal-dual method and their variations. We give theoretical guarantees for the performance of our algorithms and also present computational results which support their good performance in practice.