7 papers
Tighter relaxations for MAP-MRF optimization via Singleton Arc Consistency
Asaf Lev-Ran, Pavel Arkhipov, Vladimir Kolmogorov
We consider the MAP-MRF inference task, that is, minimizing a function of discrete variables represented as a sum of unary and pairwise terms. A prominent approach for tackling thi…
Blossom VI: A Practical Minimum Weight Perfect Matching Algorithm
Pavel Arkhipov, Vladimir Kolmogorov
Minimum weight perfect matching is a fundamental problem in combinatorial optimization. Since 2009, Blossom V has been the leading practical implementation. We present Blossom VI,…
Near-Optimal Parallel Approximate Counting via Sampling
David G. Harris, Vladimir Kolmogorov, Hongyang Liu +2
The computational equivalence between approximate counting and sampling is well established for polynomial-time algorithms. The most efficient general reduction from counting to sa…
A Fast Approximation Algorithm for the Minimum Balanced Vertex Separator in a Graph
Vladimir Kolmogorov, Jack Spalding-Jamieson
We present a family of fast pseudo-approximation algorithms for the minimum balanced vertex separator problem in a graph. Given a graph with vertices and edges, a…
Greedy matroid base packings with applications to dynamic graph density and orientations
Pavel Arkhipov, Vladimir Kolmogorov
Greedy minimum weight spanning tree packings have proven to be useful in connectivity-related problems. We study the process of greedy minimum weight base packings in general matro…
Faster algorithms for packing forests in graphs and related problems
Pavel Arkhipov, Vladimir Kolmogorov
We consider several problems related to packing forests in graphs. The first one is to find edge-disjoint forests in a directed graph of maximal size such that the indegree…