TY - CONF
T1 - Distributions on level-sets with applications to approximation algorithms
T2 - 42nd IEEE Symposium on Foundations of Computer Science, 2001. Proceedings
Y1 - 2001
A1 - Srinivasan, Aravind
KW - Approximation algorithms
KW - approximation guarantee
KW - approximation theory
KW - bounded-degree graphs
KW - computational geometry
KW - Concrete
KW - fixed-weight vectors
KW - group Steiner tree problem
KW - level-sets
KW - linear-time algorithm
KW - low-congestion multi-path routing
KW - marginal distributions
KW - maximum coverage versions
KW - negative correlation properties
KW - partial vertex cover problems
KW - trees (mathematics)
AB - 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.
JA - 42nd IEEE Symposium on Foundations of Computer Science, 2001. Proceedings
PB - IEEE
SN - 0-7695-1116-3
M3 - 10.1109/SFCS.2001.959935
ER -