101 citations · 104 across the 5 of their papers we have counts for
15 papers
Simple parallel estimation of the partition ratio for Gibbs distributions
David G. Harris, Vladimir Kolmogorov
We consider the problem of estimating the partition function of a Gibbs distribution with the Hamiltonian . As shown in [Ha…
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…
Generalized minimum 0-extension problem and discrete convexity
Martin Dvorak, Vladimir Kolmogorov
Given a fixed finite metric space , the {\em minimum -extension problem}, denoted as ${\tt 0\mbox{-}Ext}[μ]$, is equivalent to the following optimization problem: minimiz…
One-sided Frank-Wolfe algorithms for saddle problems
Vladimir Kolmogorov, Thomas Pock
We study a class of convex-concave saddle-point problems of the form where is a linear operator, is th…