13 citations · 38 across the 6 of their papers we have counts for
4 papers · 1 filter
Ignorance is Almost Bliss: Near-Optimal Stochastic Matching With Few Queries
Avrim Blum, John P. Dickerson, Nika Haghtalab +3
The stochastic matching problem deals with finding a maximum matching in a graph whose edges are unknown but can be accessed via queries. This is a special case of stochastic -s…
Multiway Cut, Pairwise Realizable Distributions, and Descending Thresholds
Ankit Sharma, Jan Vondrák
We design new approximation algorithms for the Multiway Cut problem, improving the previously known factor of 1.32388 [Buchbinder et al., 2013]. We proceed in three steps. First, w…
On the Approximation of Submodular Functions
Nikhil R. Devanur, Shaddin Dughmi, Roy Schwartz +2
Submodular functions are a fundamental object of study in combinatorial optimization, economics, machine learning, etc. and exhibit a rich combinatorial structure. Many subclasses…
An O(log(n)) Fully Dynamic Algorithm for Maximum matching in a tree
Manoj Gupta, Ankit Sharma
In this paper, we have developed a fully-dynamic algorithm for maintaining cardinality of maximum-matching in a tree using the construction of top-trees. The time complexities are…