3 citations · 7 across the 4 of their papers we have counts for
4 papers
A Rounding by Sampling Approach to the Minimum Size k-Arc Connected Subgraph Problem
Bundit Laekhanukit, Shayan Oveis Gharan, Mohit Singh
In the k-arc connected subgraph problem, we are given a directed graph G and an integer k and the goal is the find a subgraph of minimum cost such that there are at least k-arc dis…
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering
Shayan Oveis Gharan, Luca Trevisan
Spectral partitioning is a simple, nearly-linear time, algorithm to find sparse cuts, and the Cheeger inequalities provide a worst-case guarantee for the quality of the approximati…
Submodular Maximization by Simulated Annealing
Shayan Oveis Gharan, Jan Vondrák
We consider the problem of maximizing a nonnegative (possibly non-monotone) submodular set function with or without constraints. Feige et al. [FOCS'07] showed a 2/5-approximation f…
Online Stochastic Matching: Online Actions Based on Offline Statistics
Vahideh H. Manshadi, Shayan Oveis Gharan, Amin Saberi
We consider the online stochastic matching problem proposed by Feldman et al. [FMMM09] as a model of display ad allocation. We are given a bipartite graph; one side of the graph co…