Distributions on level-sets with applications to approximation algorithms

TitleDistributions on level-sets with applications to approximation algorithms
Publication TypeConference Papers
Year of Publication2001
AuthorsSrinivasan A
Conference Name42nd IEEE Symposium on Foundations of Computer Science, 2001. Proceedings
Date Published2001/10/08/11
ISBN Number0-7695-1116-3
KeywordsApproximation algorithms, approximation guarantee, approximation theory, bounded-degree graphs, computational geometry, Concrete, fixed-weight vectors, group Steiner tree problem, level-sets, linear-time algorithm, low-congestion multi-path routing, marginal distributions, maximum coverage versions, negative correlation properties, partial vertex cover problems, trees (mathematics)

We consider a family of distributions on fixed-weight vectors in {0, 1}t; these distributions enjoy certain negative correlation properties and also satisfy pre-specified conditions on their marginal distributions. We show the existence of such families, and present a linear-time algorithm to sample from them. This yields improved approximation algorithms for the following problems: (a) low-congestion multi-path routing; (b) maximum coverage versions of set cover; (c) partial vertex cover problems for bounded-degree graphs; and (d) the Group Steiner Tree problem. For (a) and (b), the improvement is in the approximation ratio; for (c), we show how to speedup existing approximation algorithms while preserving the best-known approximation ratio; we also improve the approximation ratio for certain families of instances of unbounded degree. For (d), we derive an approximation algorithm whose approximation guarantee is at least as good as what is known; our algorithm is shown to have a better approximation guarantee for the worst known input families for existing algorithms.