Deterministic Sampling Algorithms for Network Design

Deterministic Sampling Algorithms for Network Design,10.1007/s00453-009-9344-x,Algorithmica,Anke van Zuylen

Deterministic Sampling Algorithms for Network Design   (Citations: 1)
BibTex | RIS | RefWorks Download
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. (J. ACM 54(3):11, 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. (J. ACM 54(3):11, 2007).
Journal: Algorithmica , vol. 60, no. 1, pp. 110-151, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: