2013/07/08 by Nicholas J. A. Harvey, Harvey, Nicholas J. A., Neil Olver +1 · 2 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #cs.DS #math.CO
paper · pdf · doi:10.48550/arxiv.1307.2274
arxiv created 2013/07/08 · openalex publication_date 2013/07/08 · arxiv updated 2013/07/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Pipage rounding is a dependent random sampling technique that has several interesting properties and diverse applications. One property that has been particularly useful is negative correlation of the resulting vector. Unfortunately negative correlation has its limitations, and there are some further desirable properties that do not seem to follow from existing techniques. In particular, recent concentration results for sums of independent random matrices are not known to extend to a negatively dependent setting. We introduce a simple but useful technique called concavity of pessimistic estimators. This technique allows us to show concentration of submodular functions and concentration of matrix sums under pipage rounding. The former result answers a question of Chekuri et al. (2009). To prove the latter result, we derive a new variant of Lieb's celebrated concavity theorem in matrix analysis. We provide numerous applications of these results. One is to spectrally-thin trees, a spectral analog of the thin trees that played a crucial role in the recent breakthrough on the asymmetric traveling salesman problem. We show a polynomial time algorithm that, given a graph where every edge has effective conductance at least κ, returns an O(κ-1 ⋅ log n / log log n)-spectrally-thin tree. There are further applications to rounding of semidefinite programs, to the column subset selection problem, and to a geometric question of extracting a nearly-orthonormal basis from an isotropic distribution.