101 citations · 355 across the 29 of their papers we have counts for
9 papers · 1 filter
A simpler and parallelizable -approximation algorithm for Sparsest Cut
Vladimir Kolmogorov
Currently, the best known tradeoff between approximation ratio and complexity for the Sparsest Cut problem is achieved by the algorithm in [Sherman, FOCS 2009]: it computes $O(\sqr…
OrderedCuts: A new approach for computing Gomory-Hu tree
Vladimir Kolmogorov
The Gomory-Hu tree, or a cut tree, is a classic data structure that stores minimum - cuts of an undirected weighted graph for all pairs of nodes . We propose a new app…
A computational study of Gomory-Hu construction tree algorithms
Vladimir Kolmogorov
This paper studies algorithms for computing a Gomory-Hu tree, which is a classical data structure that compactly stores all minimum - cuts of an undirected weighted graph. We…
A new notion of commutativity for the algorithmic Lovász Local Lemma
David G. Harris, Fotis Iliopoulos, Vladimir Kolmogorov
The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combinatorics which can be used to establish the existence of objects that satisfy certain properties. The breakthr…
Parameter estimation for Gibbs distributions
David G. Harris, Vladimir Kolmogorov
We consider Gibbs distributions, which are families of probability distributions over a discrete space with probability mass function of the form f…
Extensions of the Algorithmic Lovasz Local Lemma
Vladimir Kolmogorov
We consider recent formulations of the algorithmic Lovasz Local Lemma by Achlioptas-Iliopoulos-Kolmogorov [2] and by Achlioptas-Iliopoulos-Sinclair [3]. These papers analyze a rand…
A Faster Approximation Algorithm for the Gibbs Partition Function
Vladimir Kolmogorov
We consider the problem of estimating the partition function of a Gibbs distribution with a Hamilton , or more precisely the logarithm of the…
Commutativity in the Algorithmic Lovasz Local Lemma
Vladimir Kolmogorov
We consider the recent formulation of the Algorithmic Lovász Local Lemma [10,2,3] for finding objects that avoid `bad features', or `flaws'. It extends the Moser-Tardos resampling…
Minimizing a sum of submodular functions
Vladimir Kolmogorov
We consider the problem of minimizing a function represented as a sum of submodular terms. We assume each term allows an efficient computation of {\em exchange capacities}. This ho…