18 citations · 109 across the 28 of their papers we have counts for
6 papers · 1 filter
On the cut-query complexity of approximating max-cut
Orestis Plevrakis, Seyoon Ragavan, S. Matthew Weinberg
We consider the problem of query-efficient global max-cut on a weighted undirected graph in the value oracle model examined by [RSW18]. Graph algorithms in this cut query model and…
Formal Barriers to Simple Algorithms for the Matroid Secretary Problem
Maryam Bahrani, Hedyeh Beyhaghi, Sahil Singla +1
Babaioff et al. [BIK2007] introduced the matroid secretary problem in 2007, a natural extension of the classic single-choice secretary problem to matroids, and conjectured that a c…
New Query Lower Bounds for Submodular Function MInimization
Andrei Graur, Tristan Pollner, Vidhya Ramaswamy +1
We consider submodular function minimization in the oracle model: given black-box access to a submodular set function , find an element of $\arg\mi…
Optimal Single-Choice Prophet Inequalities from Samples
Aviad Rubinstein, Jack Z. Wang, S. Matthew Weinberg
We study the single-choice Prophet Inequality problem when the gambler is given access to samples. We show that the optimal competitive ratio of can be achieved with a single…
Computing exact minimum cuts without knowing the graph
Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg
We give query-efficient algorithms for the global min-cut and the s-t cut problem in unweighted, undirected graphs. Our oracle model is inspired by the submodular function minimiza…
Parallel Algorithms for Select and Partition with Noisy Comparisons
Mark Braverman, Jieming Mao, S. Matthew Weinberg
We consider the problem of finding the highest element in a totally ordered set of elements (select), and partitioning a totally ordered set into the top and botto…