8 papers
Multiplicative Weights for Mixed Block Constraints and Maximum Multicommodity Flow
Vladimir Kolmogorov
We study multiplicative-weights (MWU) algorithms for block-separable feasibility problems containing both packing and covering constraints. Each iteration optimizes a weighted line…
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…
Fast Approximation Algorithms for Balanced Edge and Vertex Separators
Vladimir Kolmogorov, Jack Spalding-Jamieson
We present a family of fast pseudo-approximation algorithms for the minimum balanced element cut problem in a graph, which includes vertex and edge separators. Given a graph $G=(V,…
Matroid Base Packings: Improved Dynamic Matroid Density and Combinatorics of Tree Packings
Pavel Arkhipov, Vladimir Kolmogorov
Greedy minimum-weight spanning tree packings are an important tool in graph connectivity algorithms. We study the corresponding process of greedy base packing in matroids, followin…
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…
Bounded indegree -forests problem and a faster algorithm for directed graph augmentation
Pavel Arkhipov, Vladimir Kolmogorov
We consider two problems for a directed graph , which we show to be closely related. The first one is to find edge-disjoint forests in of maximal size such that the inde…