7 papers
Improved Error Bounds for Pure Differentially Private Continual Counting via Matrix Factorization
Pavel Arkhipov, Nikita P. Kalinin
Continual counting under pure differential privacy is one of the simplest and most well-studied problems in the continual observation model. Nevertheless, an asymptotic gap remains…
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,…
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…
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…