Deterministic Sampling Algorithms for Network Design

For several NP‐hard network design problems, the best known approximation algorithms are remarkably simple randomized algorithms called Sample‐Augment algorithms in Gupta et al. (2007). The algorithms draw a random sample from the input, solve a certain subproblem on the random sample, and augment the solution for the subproblem to a solution for the original problem. We give a general framework that allows us to derandomize most Sample‐Augment algorithms, i.e. to specify a specific sample for which the cost of the solution created by the Sample‐Augment algorithm is at most a constant factor away from optimal. Our approach allows us to give deterministic versions of the Sample‐Augment algorithms for the connected facility location problem, in which the open facilities need to be connected by either a tree or a tour, the virtual private network design problem, 2‐stage rooted stochastic Steiner tree problem with independent decisions, the a priori traveling salesman problem and the single sink buy‐at‐bulk problem. This partially answers an open question posed in Gupta et al. (2007).